A.Design Issues 
        1.The function of the data link layer is to provide the network layer with a "reasonably clean" service between 
          routers. 
             a.Three basic types are widely used: 
                    unacknowledged connection-less 
                    acknowledged connection-less 
                    acknowledged connection-oriented 
             b.To carry out its function, it carves the data from the network layer into frames and puts acknowledgment 
               and error control information in a header, allowing flow control and error control. 
             c.Similar issues appear at the transport layer which offers similar services to the applications layer. 

               Why repeat error control and flow control at the data link layer when it must be done at the transport 
               layer? 

               Answer: Shorter strings (frames as opposed to messages) are posed over shorter distances 
               (router-to-router, as opposed to host-to-host). Without control at the data link layer, it might not be 
               possible to pass messages ungarbled--that is particularly true for microwave cable and wireless 
               transport--and much less true for optical fibers. 

               Note: ATM does not control errors in the data that it receives from the network layer, although it does 
               control error in its own headers. This is because it was built for optical fibers and this causes trouble when 
               ATM is applied to wireless communications. 

        2.Framing 
             a.To create frames from a string of bits, one must have some way of marking the beginning and the end of the 
               frame as well as controlling flow and errors. 
             b.Approaches to frame marking: 
                    Character count: This method uses a field in the header to specify the number of characters in a 
                    frame. Drawback: The count is garbled by a transmission error that messes up the character count. 
                    A check-sum may indicate that the frame has a problem, but it doesn't tell how to recover 
                    synchronism. 

                    Starting and ending characters (with character stuffing): Each frame can start with the ASCII 
                    sequence DLE STX and end with DLE ETX, where DLE = Data Link Escape, STX = Start of 
                    Text, and ETX = End of Text. 

                    To avoid confusing a DLE that occurs in text with the beginning or end of the frame, it is doubled in 
                    text by the addition of an extra DLE that is removed before transmission to the network layer. 
                    Drawback: Its close tie with ASCII transmission makes it too specialized. 

                    Start with ending flags (with bit stuffing): Each frame may begin and end with a special bit sequence 
                    (a flag) such as 01111110. An extra 0 is added after five consecutive 1's and then removed at the 
                    receiver. 
                    Violations of physical layer coding: Some transmission schemes use coding to represent data. For 
                    example, Manchester Coding (which is used in the phone system to avoid drift in AC-coupling) uses 
                    1-0 for a 1 and 0-1 for a 0. A combination like 1-1 or 0-0 that does not occur in data can be used 
                    for framing. 

                    Fig. 3-3 Bit stuffing. (a)The original data. (b) The data as they appear on the line. (c)The data as 
                    they are stored in the receiver's memory after de-stuffing. 

   B.Error Control, Flow Control 
        1.Real channels always have some probability of causing errors in some bits or dropping a frame entirely. 

          Fig. 3-4 

             1.To control errors, information is sent in the header to the receiver to allow it to determine whether there is 
               an error. [We will shortly discuss in detail how this is done in practice, but it always involves redundancy. 
               Suppose, for example, one simply doubled every bit. If a 01 or a 10 arrives, then there is obviously an 
               error--although it is not clear whether the bit is a zero or a one.] 
             2.The protocol may use an error-correcting code, in which case the receiver will try to correct the error if it 
               finds one or an error-detecting code, in which case it can only find errors (as above). 
                    If it finds no error or corrects the error, the receiver sends a positive acknowledgment. 
                    If it does not or cannot correct the error, it sends a negative acknowledgment. 
             3.When the sender sends a packet, it starts a timer in case the frame is destroyed; if the timer goes off, the 
               sender resends. 
             4.Note that the acknowledgment can have errors or be destroyed; so, the receiver must be able to detect 
               and discard duplicate packets. 
        2.Flow Control is done by having the receiver tell the sender in an acknowledgment that it cannot accept any more 
          packets (or it might give advance warning that it will accept only n packets). When it is ready to accept more 
          packets, it sends a control frame to the sender, letting it know. 
        3.Error types: 
             a.Random error: individual bits are randomly error-ed (typical of fibers--easier to detect and correct). 
             b.Burst error: a group of bits are all error-ed (typical of wireless transmission--harder to detect and correct). 
        4.Hamming codes 
             a.A typical frame has m message bits and r check bits. The total number of bits n=m+r. Consider two n-bit 
               codewords. 
 
 

               TheHamming distance d is defined as: 
 
 

             b.All 2^m possible data messages are valid but all 2^n codewords are not. 

               For all allowed codewords, the minimum Hamming distance between them is the Hamming distance of the 
               code. 
                    To detect d errors, a d+1 code is needed because no d errors can change a valid codeword into 
                    another valid codeword. 
                    To correct d errors a 2d+1 code is needed because with d errors, the error-ed codeword is still 
                    closer to the correct codeword than any other codeword. 

             c.Simple examples 
                    parity bit: Add one bit to every eight bits so that the total number of 1's is even; e.g. 

                    10110101->10110101 |1 
                    10110001->10110001 |0 

                    This code is a d=1 code that can detect single errors (often used in old 1200 baud modems, for 
                    example). 
                    simple error-correcting: a code with four valid codewords: 0000000000, 0000011111, 
                    1111100000, 1111111111. This code has d=5 and can correct double errors; e.g. 

                    0000000111->0000011111 

                    With 3 errors -> WRONG CODEWORD. Same with the parity bit; two errors would not be 
                    detected. 
             d.IMPORTANT NOTE: NO (finite) CODE CAN CORRECT ALL ERRORS! 
             e.Hamming code (to correct all 1 bit errors) 
                    All 2^m messages have n illegal codewords at a distance 1; achievable by inverting all the bits in a 
                    legal codeword one by one. So, there are n+1 bits associated with each codeword (including the 
                    legal codeword). 

                    Hence, (n+1)2^m <= 2^n becomes (m+r+1) <= 2^r 

                    This limit is achieved using Hamming's procedure. Tanenbaum describes the general procedure (a bit 
                    critically); we will consider an example with seven bit codewords. 
                       1.Take data bits [1001000 = H (in ASCII)] and distribute them among codeword slots, leaving 
                         powers of 2 empty; label the slots in binary notation. 
                       2.In the slot 2^0, put the XOR of all a[ijkl], for which l=1; in the slot 2^1, put the XOR of all 
                         a[ijkl], for which k=1; etc. 
                       3.At the receiver, calculate the XOR of all bits with a 1 in the same digit, including check bits. If 
                         the string is correct, then all results are 0 since the number of 1's is even! Non-zero results 
                         point to the digit of the incorrect bit. 
                       4.This code lends itself readily to implementation in digital logic. 
                    The Hamming code does not correct bursts, but that can be fixed re-organizing the data in matrices 
                    in which the transmitted data are in rows and correction is done in columns. A burst that wipes out 
                    the middle transmission makes at most one error per row and is correctable. 
        5.Polynomial Codes (cyclic redundancy codes or CRC codes) 
             a.These codes are used for error detection (although error correction codes can be built using similar 
               principles). 
             b.Bit strings of length k are regarded as the coefficients of a polynomial of degree k-1: 
               110001 -> 1*x^5 + 1*x^4 + 0*x^3 + 0*x^3 + 0*x^2 + 0*x^1 + 1*x^0 = x^5 + x^4 + 1 

                    Polynomial arithmetic is done modulo 2. There are carries for addition or borrows for subtraction 
                    (both are equivalent to an XOR). 
                    Long division is done analogous to the usual long division, but the subtraction is modulo 2. 
             c.Procedure 
                    Sender and receiver agree on a generator polynomial G(x). Note: If M(x) is the polynomial 
                    corresponding to the message to be sent, one must have degree [M(x)] = m-1 > degree [G(x)] = r. 
                    In our example, 

                    M(x) <- 1101011011 (m=10) 
                    M(x) = x^4 + x^8 + x^6 + x^4 + x^3 + x + 1 
                    G(x) <- 10011 (r=4) 

                    The goal is to obtain a transmitted frame whose additional bits (checksum bits) lead to a T(x) that is 
                    divisible by G(x). To do that we (a) add r 0's at the end of the frame obtaining a polynomial 
                    x^r*M(x), (b) divide G(x) into x^r*M(x) modulo 2, and (c) subtract (which is the same as adding) 
                    the remainder to get T(x). 
                    At the receiver, T(x)->R(x); divide R(x)/G(x). If it is not equal to zero, there is an error. 
             d.Power of the Method 
                    R(x)/G(x) = [T(x) + E(x)]/G(x) = E(x)/G(x) 

                    The only errors that slip by are the ones that are divisible by G(x). One can now design G(x) to 
                    catch all common errors. 
                    Single errors have E(x) = x^i; if G(x) has two or more terms, then all single errors are detected. 
                    Double errors have E(x) = x^i + x^j = x^j(x^(i-j)+1); if G(x) does not divide x^k +1 up to the frame 
                    length then all double errors are detected. Example: x^15 + x^14 + 1 protects all frames up to k = 
                    32,767. 
                    If the error has an odd number of bits, E(x) has an odd number of terms. No polynomial with an odd 
                    number of terms is divisible by x+1 (see Tanenbaum for proof, p. 189). Hence, if G(x) contains x+1, 
                    then all errors with odd numbers of bits are caught. 
                    All burst errors of length <= r have an E(x) that is not divisible by G(x) and are detected. 
                    SIMPLE SHIFT REGISTER CIRCUITS CAN BE MADE TO IMPLEMENT THIS 
                    CHECKSUM ALGORITHM IN HARDWARE. 
             e.Certain polynomials have become international standards: 

               CRC-12 = x^12 +x^11 + x^3 + x^2 + x + 1 (used for 6 bit characters) 

               CRC-16 = x^16 + x^15 + x^2 + 1 (used for 8 bit characters) 

               CRC-CCITT = x^16 + x^12 + x^5 + 1 (used for 8 bit characters) 

               Note: All three contain x+1 as a factor. 

  C.Tanenbaum's Sample Protocols 
        1.In pp. 190-219 (Sec. 3.3-3.4), Tanenbaum describes a series of six connection-oriented, reliable protocols of 
          increasing complexity that give a useful example of how protocols can work. 
             a.The first three are simplex and pass data in one direction. The second three are duplex and pass messages 
               in both directions. 
             b.While the protocol receives/sends information from/to the network layer, adds/subtracts a header, and 
               sends/receives it to/from the physical layer, it is best to think of the information as being transmitted 
               between the data link layers in the two hosts and being communicated in the header. [The info used by the 
               network layer is along for the ride]. 
             c.The header has three basic fields: 
                    kind = data (used for a standard data packet), ack (used for positive acknowledgments of frames; 
                    w/o data: protocol 6), nak (used for negative acknowledgment of damaged frame received; w/o 
                    data: protocol 6) 
                    seq = sequence number of frame sent 
                    ack = acknowledgment number of last frame received 
        2.Simplex Protocols (one way) 
             a.Protocol 1 (utopia): Assumes no error or flow control is needed; packets are sent at a regular rate. 
             b.Protocol 2 (stop-and-wait): Still assumes no error control is needed, but the receiver sends back a dummy 
               frame to "wake up" the sender. 
             c.Protocol 3 (par = positive acknowledgment with retransmission): Error control is now used. A 1-bit 
               sequence number is sent (0 or 1). The sender has a timer and resends if it goes off (either an error-ed 
               acknowledgment or no acknowledgment is received). 
        3.Duplex Protocols (with sliding windows) 
             a.Since data is being sent both ways, acknowledgments of the last (or several last) data frames received can 
               be sent with the next data frame to be sent. This is called piggybacking and is used by protocols 4-6. One 
               doesn't want to wait forever to acknowledge. Protocol 6 sets a timer and if there is no data frame to 
               piggyback on, it sends an acknowledgment frame. 
             b.Sliding Window Protocols (3-6) allow frames to arrive garbled or out of order within a certain order. 
               However, they are buggered when needed and always transmitted to the network layer in order. There is a 
               sending window which determines the sequence numbers that can be sent and a receiving window which 
               determines the frames that can be received. [In protocols 3 & 4, both windows switched between 0 and 
               1]. 
             c.Protocols 1-4 deal inefficiently with finite transmission times and timeout intervals. Protocols 5 & 6 address 
               this difficulty using a pipelining strategy in which frames inside the sending window are sent at a regular rate 
               without waiting for the acknowledgment. There are two strategies for dealing with errors: 
                    Go back n: Everything after the error frame is thrown out. 

                    Selective repetition: Subsequent good frames are buffered and held. 
             d.Much of the complexity in Protocol 6 is related to the need for separate timers to deal with the lage variety 
               of possibilities. 
  D.Protocol Specification 
        1.Since protocols can be complicated, it is of interest to find formal mathematical methods for examining the 
          protocols. 

          Note: The approaches that we will describe can be applied to a wide variety of computer programs and digital 
          devices. 

          The approaches used are based on the concept of a finite state machine or a protocol machine that go back at 
          least to Turing. One finds all the states that the system can be in and the transitions to other states. 

          One state is the initial state, where the system begins. Using techniques from graph theory (reachability analysis), 
          one can determine whether all states can be reached or the system can deadlock. 
        2.Example: (Tanenbaum's Protocol 3) Each state is labeled XYZ: 

          X = 0,1: Sender's sequence number 
          Y = 0,1: Receiver's sequence number 
          Z = 0,1,A,- 
          0: 0 Frame in channel 
          1: 1 Frame in channel 
          A = acknowledgment frame or channel 
          -: Empty channel 

             a.In normal operation, we cycle between 1->2->3->4. 
             b.When frames are lost, we go to one of the four corners and spend some time before returning to regular 
               operation. 
        3.There are other approaches to describing finite state machines. Tanenbaum discusses Petri nets. 
   E.Widely Used Protocols 
        1.HDLC (High-level data link control) 
             a.This protocol is descended from IBM's SDLC (synchronous data link control) -> ADCCP (advanced data 
               communication control procedure) [ANSI] & HDLC [ISO] -> LAPB (CCITT) to be used in X.25. 
             b.The protocol is bit-oriented and uses bit stuffing for data transparency. 
 
 
 

             c.Fields: 
                    Flag delimiters 
                    Address: identifies terminals 
                    Control: sequence numbers, acknowledgments, etc. 
                    Data: from network layer--of arbitrary length 
                    Checksum: Variation of CRC-CCITT to find lost flag bytes 
 
 
 

             d.There are three frame types: information, supervisory, and unnumbered with different control fields. 
             e.Seq field = frame sequence number 
               Next = piggybacked acknowledgment 
               P/F = Poll/Final; it is used to turn on terminals. Terminals send data with P up to the last frame which has an 
               F. 
             f.Supervisory frame 
               Type field: 
                    0: Receive Ready = next frame expected when there is no frame for piggybacking 
                    1: Reject = negative acknowledgment with NEXT indicating the first frame not received correctly 
                    (used for go back n strategy) 
                    2: Receive not ready: tells senders to stop sending 
                    3: Selective reject: calls for retransmission of frame specified 
             g.Unnumbered frames are usually used for connection-less, unreliable transport. The different versions of 
               HDLC differ significantly on how they set it up. It is also used for control. Control commands include: 
                    DISC: A machine declares that it is going down 
                    SNRM: A machine announces its presence and resets sequence numbers to zero. [Meant for 
                    computer -> terminal communication]. Similar commands are used between two computers. 
                    FRMR: No checksum error but impossible semantics; a type 3 supervisory frame in LAPB (where it 
                    is not allowed). 
        2.Internet Protocols 
             a.University and business users will usually run a LAN based ethernet or some other LAN protocol and will 
               also allow home users to dial in via a modem. At the end, there is a router that connects to the Internet 
               through a leased line (T1 or T3 phone line, typically). 
             b.Companies like America Online, CompuServe, and Erols provide many modem connections and a router 
               (sometimes many). 
             c.Standard home dialup services serve as a dumb terminal, opening a shell account. This does not provide 
               Internet access. Otherwise, the home computer can be established as a full-blown host with an IP number 
               (almost always temporary and dynamically assigned). 
             d.For either a host-to-router connection or a router-to-router connection, protocols to connect them are 
               needed. Two common ones are SLIP and PPP. 
             e.SLIP: Serial Line IP (RFC loss) 
                    Framing is done using a special flag byte (0xCO) at the back. 

                    In text 0xCO -> OxDB, OxDC and 0xDB is stuffed. 
                    Recent versions do header compression (not repeating header fields that remain the same and 
                    recording only differences for fields that change) as described in RFC 1144. 

                    Note: This is important because IP headers are long, as is evident from any e-mail message. 

                    Disadvantages 
                         Does no error control 
                         Only supports IP; so it is not compatible with NetWare (Novell LAN's) and other LAN 
                         protocols 
                         IP numbers cannot be dynamically assigned 
                         There is no authentication 
                         There is no standard, and many incompatible versions exist 
             f.PPP: Point-to-Point Protocol (RFC 1661, 1662, 1663, etc.) 
                    PPP rectifies the disadvantages of SLIP and provides: 
                         Unambiguous framing 
                         A link control protocol (LCP) for bringing up and tearing down connections gracefully 
                         A network control protocol for negotiating with the network layer. A different NCP must be 
                         chosen for different network layer protocols. 
 
 
 

                    The basic structure is like HDLC with the same flag, but it is byte oriented, not bit oriented, and 
                    character stuffing rather than bit stuffing is used. 

                    Address = 11111111 -> all stations should accept the frame 

                    Control = 00000011 -> frames are unnumbered (for unreliable transport) 

                    These two frames can be removed by LCP or changed (under special circumstances) for 
                    connection-oriented, reliable service. 

                    Protocol = code for what kind of packet is in the payload: LCP, NCP, IP, IPX, AppleTalk, etc. 

                    Payload = Data from the network layer. Its length is variable up to some maximum negotiated by 
                    LCP during startup. 
 
 
 

                    LCP is responsible for establishing network options and authenticating the connection. It is also 
                    responsible for terminating a connection. By contrast, NCP is responsible for dealing with the 
                    network. 
        3.The data link layer in ATM 
             a.Recall that in the ATM protocol stack, the transmission convergence sub-layer of the physical layer 
               corresponds most closely to the OSI data link layer. 
             b.ATM segments the data in cells (53 byte packets with headers) before they get to the TC sub-layer. 
             c.The TC sublayer first calculates an 8-bit checksum called the HEC (header error control) which occupies 
               the last byte of the 5 bite header and only protects the header. The checksum uses the polynomial 
               x^8 + x^2 + x + 1 and adds 01010101 to add robustness against long strings of zero. 

               If reliable transmission at the data link layer is needed, the TC sub-layer must be modified. No uniformly 
               accepted approach exists. 

             d.The TC sub-layer must also provide idle cells when no data cells are available for synchronous transmission 
               media like SONET and OAM cells (operation and management). In addition, OAM cells can be used to 
               slow down the rate of actual data transfer. 
             e.The TC sub-layer produces SONET frames when a SONET is being used (not a trivial business since 53 
               byte packets don't fit integrally in a SONET frame). 
             f.There are no flags in ATM cells; so recognizing the beginning and end of a frame is a major pain. One does 
               it by search for a valid HEC byte: 
                    In the HUNT state, one does a bit-by-bit check until a valid HEC is found. 
                    One then enters the PRE-SYNCH state in which one checks cell by cell to make sure that there is a 
                    valid HEC. When there are a certain number in a row (5-10, typically) then one moves in the 
                    SYNCH state and begins normal operation. 
 
 
 

                    After a certain number of incorrect HEC's are in a row, one returns to the HUNT state to 
                    resynchronize. 
             g.Tanenbaum complains that this approach violates the neat separation between the layers. C'est la vie in the 
               real world.