View page as slide show

Communications software, protocols and architecture

Need for flow control

  1. Communication channel is not 100% reliable
    • Transmitted packets may be lost
    • Transmitted packets may be corrupted
    • Transmitted packets may be replicated
  2. Limited buffer size
    • Receiver needs time to handle the packets.
    • Packets waiting to be handled are stored in buffer.

Stop-and-wait

  • Solution for limited buffer size problem
  • Use of Acknowledgement PDU (ACK)
    • When receiver gets DATA PDU it sends ACK to sender
    • Sender may not send new DATA PDU before it gets ACK
  • Deadlock when packet is lost
    • Sender may not send new packet without ACK
    • receiver may not send ACK without getting packet

Timers

  • To avoid deadlocks Timers can be used.
    • If sender do not get ACK within certain time, timer will timeout
    • Sender retransmits the previous data packet
  • Lost ACK causes receiver to get same message twice
    • Need a method to distinguish retransmission e.g. retransmission flag in message.

Corrupted packets

  • Bit error ratio (BER) > 0
  • Corrupted packets can be identified for example by calculating checksums.
  • Receiver can send NAK (negative acknowledgement) PDU to inform sender about corrupted packet
    • Sender now knows it should resend the previous DATA PDU, just like in case of timeout.

RDATA and corrupted packets problem

  • Corrupted ACK and RDATA may cause receiver to believe that resent data is actually new data.
    • Packet duplication
  • Solution: Instead of general RDATA for retransmissions, use numbering for packets.
    • Packet number will tell receiver if this is a copy or not.

Mixed ACKs in lossy channel

  • Problem: too short timeout period for channel
  • solution: numbering the acknowledgements
  • Minimum time for time timeout:
    DATA PDU transmission time + PDU handling time + ACK transmission time
  • transmission time may vary when using multihop system
    • congestion in different parts of network
  • Too long timeouts will hurt performance.

Latency problem

  • High latency causes sender to be idle most of the time and slows down transmission when using stop-and-wait approach
  • example, slow satellite link
    • msg size = 1000 bits (frame), transmission speed 64kbit/s
    • signal speed == speed of light, distance 72 000 km (Geostationary satellites are at height of = 35,786 km),
    • sending one message thus takes 1 000 b / 64 000 b/s = 15.6 ms thus transmitting the signal takes 72000km/300000 km/s = 240 ms
    • getting ACK for data will thus take 240*2+15.6 ms +time for sending ack+time for handling the incoming data before sending ACK. ~ 0.5s
    • Even if we forget the message handling overhead the sender will idle 480/480+15.6 ~ 97% of the time. only 3% of channel is in use.

Frames and windows

  • In lower layers transmitted data is divided in smaller messages to avoid too many retransmissions in unreliable communication channel
    • lower layer messages are called frames. (commonly on layer 2)
  • In order to use channel more efficiently with high latency networks several frames can be sent one after another instead of waiting acknowledgement.
  • The amount of frames that is sent before ack will arrive for first frame is called Window
    • Optimal size of window is the maximum amount of messages that can be sent
    • In previous example optimal window size would be 495.6 ms /15.6 ms/frame = 31 frames

Piggybacking

  • Sending and handling ACK PDU's causes overhead.
  • When data is sent both ways, the ACK message can be sent along the data (e.g. piggyback the data PDU)
  • Sending ACK can wait until there is actual data to be sent
    • Sent ACK can contain the serial number of last arrived packet and thus Acknowledges all packets to that point as arrived.
    • Postponing ACK sending too long will cause unnecessary retransmissions
    • Good to have timeouts for ACK sending to avoid lock situations.
      • Timer starts when packet to be acknowledged arrives.

Sliding window mechanisms

  • Developed for data link and transport layer flow control
  • Tries to solve all the aforementioned problems
  • Relies that all DATA PDU's have serial numbers
    • Serial numbers can repeat after predetermined interval
    • 0,1,2, …., MAX,0,1,2… (mod max)
    • MAX determines the amount of bits required for serial number
      • MAX is usually 2^n -1 where n determines the amount of bits used
  • Sending window
    • senders list of packets that have been sent but not acknowledged
  • Receiving window
    • List of sequence numbers that receiver is ready to accept (may be different size than sending window)
    • Bigger receiving window allows PDUs to come in different order.
    • Window size determine the required size for receiving buffer
  • Protocol defines the maximum size for sending window MaxWS
    • Sending window grows from zero to MaxWS
    • When ACKs arrive, the acknowledged packets are dropped from window.
    • Due the rotating serial numbers, the window and frames are usually described with pie figure.
  • To avoid problems MAXimum sequence number should be at least: receiving window size + sending windows size

Recovery from PDU loss in sliding window

  • Go-Back-N ARQ
  • Selective repeat
  • Negative acknowledgement

Go-Back-N ARQ

  • If receiving window size is 1, then receiver only accept PDUs with the next sequence number, other are ignored
    • Simple for receiver, no need for buffers
  • Sender starts timer every time the bottom of window changes e.g. ACK arrives
  • When timer timeouts, the whole window of PDUs will be repeated.
    • Go-Back-N = going back through whole window in sending
    • ARQ = Automatic repeat request

Selective repeat

  • If receiving windows is bigger than 1, loss of one frame does not necessary mean that whole window has to be resent
    • Later PDU's may be stored in receiving buffers
  • Lost frames sequence number stays at the bottom of the receiving window and thus the receiving window is no longer moving.
  • In case of timeout, sender will send only the frame that has not been acknowledged and hopes the later frames will be Acknowledged once the missing frame arrives.
  • Timing determination may be hard especially with high latency.
    • Latency hits badly if the next frame has also been lost.

Negative ACK

  • NAK can be used when packet when receiver notices that the packet number is higher than expected, denoting that some packets are missing from middle.
    • NAK can acknowledge arrival of packets with smaller sequence number.
  • When receiving window is 1, sender has to send frames

Dynamic window size

  • Fixed size window can cause extensive amount of retransmissions if the receiver is heavily loaded
    • e.g. several connections to be handled from different sources
    • receiver do not acknowledge arrived packets quick enough →retransmission
    • retransmissions cause more packets to arrive → buffers get filled → slower response.
  • Remedies
    • Sender will slow down it sending when the acknowledgements start to arrive late e.g. reduces the window size.
    • Receiver informs the sender how big window it can currently handle (credits)

Credit

  • During opening the connection the window size is negotiated normally.
  • The receiver is only one who knows about its load, and thus it should be the one to decide the window size.
  • The ACK messages contain now space for credit parameter.
    • Credit parameter tells the sender what the size to which receiver wants to change the window size.
    • Zero credit means that receiver wants sender to quit sending new packets for time being.
  • Credits arriving in wrong order, may cause problem.
    • Adding sequence number to ACKs (not just number to state which packets it acknowledges), prevents the wrong window size
Last modified: 2013/07/01 14:42