CEN 4500C Fundamentals of Computer Communication Networks

Last modified 2/6/95.

Data Link Control

• A. General Overview

  Datalink protocols assume that the connected nodes have some way to transfer frames of data from one to the other, and that the receiver can detect errors when they occur in a frame. These topics were considered in earlier pages.

  Here we consider the problem of managing the shared link between two or more nodes. First we consider possible configurations, then we consider protocols used to assure delivery of error-free frames in correct order.

• B. Configurations
  • Topology

    A link may be

    • point-to-point, or
    • multipoint.
    Point-to-point links have exactly two nodes attached to them, and so do not require addressing (it is implicit who is sending and who is receiving by the link used). Multipoint links require addressing: if there is a distinguished node (a Master or primary station), and all communication that takes place either has it as the source or the destination, then only the address of the undistinguished (Slave or secondary) node need be included. Otherwise, both the source and the destination address must be present. Usually, address recognition at this level is done in hardware. The interface card may not even capture the frame if the address does not match. If the address does match, the interface buffers the frame and sends an interrupt (or is polled) by the main CPU on the node, which then sets up a DMA into main memory where the frame is processed further.
  • Duplexity

    The directionality and temporal constraints on use of the medium are captured by the notion of duplexity.

    • Simplex - strictly one-way communication.
    • Half-duplex - communication in one direction at a time.
    • Full duplex - simultaneous communication in both directions.
    Simplex links are often used as parts of a full duplex connection, and may be used for true simplex communication in sensor networks, for monitoring, and in broadcast radio and television. There is also satellite distributed data broadcast, for distribution of price lists, weather information, etc., which is simplex. Half-duplex links usually require that echo suppressors, directional amplifiers and other electronics change state when the direction of transmission changes on the link. This involves some transition time, which is to be avoided if possible.
  • Line Discipline

    Which node is eligible to transmit and when is the subject of line discipline. This is our main topic at the link and medium access layer, since this is where the protocols come into play.

    • Peer (balanced, symmetric) protocols

      There is no distinguished station to control the access to the shared medium, so stations must function in a distributed manner.

      • Contention-based - two or more stations may try to transmit at the same time, causing neither to succeed.
      • Collision-avoidance - still contention-based, but there is an attempt to limit the likelihood of collisions.
      • Reservation methods - fixed, dynamic, and token-passing schemes may be used to prevent collisions.
    • Master-Slave (Primary-secondary, unbalanced, asymmetric) protocols

      A primary station directs the secondary station(s), and usually all communication between secondaries must go through the primary. The primary uses polling to determine whether a secondary has data to send, and select to determine whether a secondary is ready to receive data.

      • Basic Select

        The primary sends a SEL to the secondary station it wants to send data. The selected station either ACKs if it can receive the data or NAKs if it can't. If it can, the primary sends it the data and it ACKs the frame if it was good.

      • Fast Select

        The primary sends a SEL and the data frame without waiting for the secondary to ACK the SEL first. If the secondary was ready, it ACKs as usual if the frame was good. Otherwise, it NAKs the frame (if it was not ready or if the frame was damaged).

      • Basic Poll

        The primary polls a secondary station by sending it a POLL frame. If the secondary has data, it responds with a data frame else it NAKs the POLL. The primary ACKs the data frame if it was received correctly, or NAKs it otherwise.

      • Roll-call Poll

        The primary polls each station individually, waiting for a NAK or data from each one before polling the next. The POLL for the next station can be pipelined following the ACK for the current one on multidrop lines.

      • Hub Poll

        The primary polls the farthest station first. Each secondary station, when it receives a poll, sends data if it has any, then polls the next nearest station. The nearest station polls the primary, which informs it that all the stations have been polled. The primary then ACKs all the data frames it received, and starts the next poll. This is most useful in half-duplex environments, since the cost of changing the direction of the line is paid only twice per cycle (the minimum possible) rather than twice per station. The line must be multidrop, of course. Pipelining accounts for the gain here.

    • Hybrid

      A hybrid scheme may use a primary station to set up communication resources for a pair (or a set) of secondaries, using one method to allow a secondary to request a reservation and then using reservation techniques for the secondaries to carry out their conversation. These are used in some LANs and especially in satellite networks.

• C. Data Link Protocols
  • 1. General Model

    The data link protocol must provide for

    • Link management - a communicating pair must be able to
      • Establish a link,
      • Transfer data, and
      • Terminate the link.
    • Pacing - the receiver must not be sent frames faster than it can handle them
    • Error handling - the receiver must be able to detect damaged frames and obtain corrected ones
    • Sequencing - the receiver must be able to detect missing and duplicate frames
  • 2. Data Link Protocols - Description, Assumptions & Requirements
    • i. Utopia - a hopelessly optimistic protocol

      The sender sends frames one after the other, without waiting for any ACKs. There is no way to recover from lost or damaged frames.

      • 1. Simplex channel
      • 2. Error-free channel
      • 3. Arbitrarily fast receiver (or arb. # buffers)
    • ii. Stop&Wait

      The sender sends a frame, then waits for the receiver to ACK or NAK. The protocol hangs if a data frame, an ACK or a NAK is lost.

      • 1. Half-duplex needed (or full duplex)
      • 2. Error-free channel
      • 3. Pacing
    • iii. PAR (Positive Ack & Retransmit) - no seq# for ACKs

      The sender transmits numbered frames to the receiver, puts the frame on the retransmission queue, starts a timer, and waits for an ACK or a NAK. If none is received before the timer expires, then the frame on the retransmission queue is retransmitted. The receiver can distinguish between new frames and retransmitted duplicates by the sequence number. Without numbered ACKs, however, the sender can misinterpret an ACK and fail to retransmit a lost or damaged packet.

      • 1. Full-duplex needed
      • 2. Errors tolerated (somewhat)
      • 3. Pacing
      • 4. Timer required for retransmission
      • 5. Need sequence number to distinguish duplicate frames
    • iv. Sliding Window Protocols in general

      Sliding window alone allows for multiple outstanding unacknowledged packets, so that the protocol performance can be improved. With automatic retransmit request (ARQ), it handles errors well. The receiver may be able to adjust the sender's window size for flow control.

      The sender has a maximum send window size, N, that is used to define the greatest difference (modulo max_seq_#) between the lowest numbered unacknowledged frame (min) and the highest numbered frame that can be sent (max). The sender keeps track of these two quantities, plus the next sequence number to use for a new data frame, i. If i > max the the sender has to wait until max is incremented to send frame i. The sender increments both max and min (modulo max_seq_#) when an ACK for min is received. The receiver also has a window, the receive window, that defines the frames it will accept. At first, the rmin = i, and rmax-rmin is the receive window size. Whenever a frame is received, the receiver acknowledges it (whether or not it is accepted). If the sequence number of the received frame j is such that rmin <= j <= rmax, and it has not already been received, then the receiver buffers it. If j = rmin, then the receiver increments both rmax and rmin (modulo max_seq_#) and passes the frame to the next higher layer. If frame j+1 was already received and buffered, then it too is passed on and the receive window shifted. This continues until frame rmin is not in a recieve buffer.

      • 1. Full-duplex needed
      • 2. Errors tolerated
      • 3. Pacing provided by window control
      • 4. Timers required for retransmission
      • 5. Need sequence number to distinguish duplicate frames
      • 6. Need sequence number for ACKs as well
    • v. Stop&Wait ARQ (One-bit SW)

      A one-bit sequence number is used, with the ACK naming the next sequence number it expects.

    • vi. Go-Back-N ARQ (ACK max, no NAK)

      The receiver typically uses cumulative ACKs, naming the next sequence number it expects. NAKs only expedite retransmission. The receiver need only have one buffer, provided it can always transfer frames to the host.

    • vii. Selective-report ARQ (ACK or NAK each frame)

      The SR (selective reject/report/retransmit) ARQ requires the receiver to have as many buffers as the sender, and to buffer frames received out of order, provided they are in the receive window. Cumulative ACKs will not inform the sender of frames correctly received out of order until the missing frame is received, so explicit ACKs are often used. NAKs are very useful with this protocol.

  • 3. Data Link Protocols - Analysis of Efficiency and Correctness

    An important parameter to consider is the number of frames that can be in transit from the sender to the receiver a one time, a.

    • a = (Prop delay)/(Frame Tx time) = (D/V)/(L/R) = DR/VL,

      where D = distance (meters), V = propagation velocity (m/s), L = frame size (bits), and R = data rate (bps).

    This normalizes the propagation delay to frame transmission time. Performance has three main components (L = total frame length, H = control and framing bits, N = number of data frames sent in a cycle, T_d is the time spent in a cycle sending data frames, T_c is the total cycle time, P = frame error rate, N_r = number of retransmissions required per data frame, on the average, so N_r+1 = average number of frames sent per successful data frame):
    • a factor due to framing and control bits added around the data in a data frame (overhead bits): U_f = (L-H)/L,
    • a factor due to the protocol itself (how much time the sender has to spend in order to send a data frame): U_p = N(T_d)/(T_c), and
    • a factor due to errors (how many data frames have to be sent on the average in order to deliver one without errors), U_e = 1/(N_r+1). Usually, U_e = 1-P.
    The overall efficiency of the system is the product of these component efficiencies, U = U_f U_p U_e.
    • i. Utopia - max utilization -

      U_p = 1.

    • ii. Stop&Wait - pacing -

      U_p = 1/(1 + 2a)

    • iii. PAR (Positive Ack & Retransmit) - no seq# for ACKs
      • Note:
      • ln(z) = Sum (n=1 to inf) [ (-1)**(n-1)(z-1)**n/n ], |z-1|<1
      • ln(1-x) = Sum (n=1 to inf) [(-1)**(n-1)(-x)**n/n] , |x| < 1
      • = Sum (n=1 to inf) [(-1)**(2n-1)x**n/n]
      • = Sum (n=1 to inf) [- x**n/n]
      • = - Sum (n=1 to inf) [x**n/n] , |x|<1
      • which for 0 < x << 1 is approximately -x.
    • iv. Sliding Window Protocols in general -

      U_p = min{1, N/(1+2a)}, where N = send window size.

      • 1. Effect of window size

        As N increases, so does U_p up to a point (when N = 1_2a).

      • 2. Limits on window size:

        There is little point to having a receive window larger than the send window, and the sum of the maximum send and receive windows must not exceed the total number of sequence numbers available.

    • v. Stop&Wait ARQ (One-bit SW)

      Like PAR, but it has sequence numbers on the ACKs.

    • vi. Go-Back-N (GBN) ARQ

      (ACK max, no NAK)

    • vii. Selective-repeat (or selective-reject) (SR) ARQ

      (ACK or NAK each frame)

    • viii. Effect of errors

      To estimate the effect of errors, the decrease in utilization due to retransmission of damaged frames must be considered. If P = frame error rate = Prob(frame is damaged), then the expected number of transmissions per success, assuming that an error only causes one frame to be retransmitted, is:

      • Nr+1 = Sum (i=1 to oo) [i P^(i-1) (1-P)] = 1/(1-P).
      This is a weighted infinite sum, with i representing the number of transmissions needed to have success, and P^(i-1) (1-P) being the probability that exactly i attempts are required (assuming that the errors are independent). P^(i-1) is the probability that the first i-1 frames are damaged, and (1-P) is the probability that the ith one is not. As long as one damaged frame does not cause other frames to be retransmitted (as it does in GBN ARQ), then this expected number of transmissions per successful transmission appears as a multiplicative factor in the utilization equation.
    • ix. Optimization

      The error rate, hence the expected number of retransmissions, increases as the frame length increases, which causes U_e to decrease. On the other hand, U_f improves as the frame length increases, since more data is packed into a frame with a fixed amount of overhead. Likewise, increasing L will decrease a, so the protocol utilization rate may also improve. Balancing these conflicting trends to obtain the best net overall utilization is an optimization problem. A parametrized formula for the overall utilization taking all these factors into account may be differentiated with respect to L, and when this derivative is set to zero and the equation solved, a local extremum will be found. By checking the utilization at this value of L as well as the limit as L -> oo, the global optimum value of L may be found, as a function of bit error rate, framing overhead, and protocol.

  • 3. Data Link Protocols - Comments on piggybacking, NAKs and ACKs
    • Piggy-backing: For piggybacking the frame format includes a field for an acknowledgement in each data frame. This avoids the high overhead of sending a control frame for no purpose but to acknowledge a received data frame, and also allows for some redundancy in acknowledgements. If the traffic is not about equal between the stations, then some form of cumulative ACK is needed, otherwise explicit ACK frames will have to be sent anyway. The receiver may not have a data frame on which to piggyback and ACK, and so may have to wait for a data frame to arrive in order to acknowledge the frame it has received. It can't wait too long, or else the sender's retransmission timer will expire, and the frame will be resent, wasting resources unnecessarily. Thus the receiver should have a piggyback timer that it sets when a frame is received and that it turns off when a piggybacked ACK is sent. If the piggyback timer expires before a return data frame arrives that can piggyback the ACK, then an ACK control frame is sent.
    • NAKs: All that NAKs do is allow the receiver to signal the sender that a frame has been damaged before the sender's retransmission timer goes off. In this sense, it is just an optimization for early retransmission.
    • Cumulative ACKs: Most common, and especially useful for GBN ARQ are ACKs that indicate that all frames up to some seqence number have been received correctly. Usually these cumulative ACKs indicate the next sequence number that the receiver expects, and so means that all the sequence numbers before that one have been received in good shape. Since the GBN receiver does not buffer out-of-sequence frames, this is the only number of interest to the sender anyway.
    • Explicit ACKs: If an ACK means only that the sequence number mentioned has been received, then this is an explicit ACK. When using Selective Repeat ARQ, this allows the sender to determine that a frame has been received out of order, and retransmit the missing frame. Unfortunately, it also means that each frame must have its own ACK, so piggybacking does not work as well if there is asymmetric traffic. It also means that there is little or no redundancy, so a damaged ACK will cause the sender to retransmit a frame that has been received in good condition. Explicit ACKs serve no purpose in GBN ARQ.
    • Block ACKs: On links with very large delay x data rate products (large frame storage capacity) and high error rates, block ACKs are sometimes used. The block ACK has two fields: one that indicates the prefix of the sequence numbers in the block, and the other a bitmap of the sequence numbers in the block. Each position in the bitmap corresponds to an ACK or a NAK for a sequence number. For example,

      		
       |SEQ #|0<--- BITMAP-->F|
      		
       | 20A |1011111101110000|
      		

      • indicates that sequence numbers 20A1, 20A8, 20AC, 20AD, 20AE, and 20AF are missing from the range 20A0-20AF.
      Block ACKs combine the redundancy of cumulative ACKS with the specificity of explicit ACKs and NAKs, at a cost of extra overhead in the ACK field (for the example, assuming that the digits are all in hexidecimal, there are 12 bits of prefix and 16 bits of bitmap for a 16-bit sequence number, using 12 more bits than either standard ACK type would use).