CS 268 - Class Notes (Data Link Protocols)

Data Link Protocols

We'll be looking at the common data link protocols used with TCP/IP. These will include Ethernet, IEEE 802.x, PPP, Transparent Bridging, and ATM.

Ethernet

Ethernet is a standard developed in 1982 by a coalition of DEC, Intel, and Xerox. Ethernet uses an access method for controlling use of the physical wire. This access method is CSMA/CD (Carrier Sense, Multiple Access with Collision Detection). Carrier Sense means that each station listens before it transmits. Multiple Access means that the medium is a shared transmission media. Collision Detection means that each station monitors while it is transmitting to detect collisions. Collision detection plays a role in limiting the length of a media due to how fast it takes a collision to be detected and recovered from.

RFC 894 specifies how an IP packet is encapsulated in an Ethernet frame. An Ethernet frame is composed of two addresses, some data, a type field, and a checksum (CRC) trailer. As shown below.


Bytes:     6          6       2         46-1500           4
      +---------+---------+-------+--------------------+------+
      |Dest addr| Src addr| Type  |     Data           | CRC  |
      +---------+---------+-------+--------------------+------+

Ethernet addresses are 48-bit addresses and are typically written in hexadecimal form with each byte separated by a '-'. e.g. XX-XX-XX-XX-XX-XX. An Ethernet frame is given a minimum length, thus the minimum data length of 46 bytes and a total minimum frame size fo 64 bytes. The Type field is given the value of 0x0800 for an IP datagram and 0x0806 for ARP frames. RFC 1340 specifies different type field values for various network protocols.

IEEE 802

The IEEE standardized a family of LAN technolgies a few years after Ethernet was out. The IEEE subdivided the Data Link Layer into two sublayers. The MAC (Media Access Control) portion deals with various access methods. The LLC (Logical Link Control) portion deals with lower level link control mechanisms. The LLC sublayer is divided into types. LLC Type 1 deals with datagram protocols. LLC Type 2 deals with connection-oriented datagram protocols. And LLC Type 3 deals with semi-reliable protocols.

The IEEE developed subcomittees to handle standardizing different pieces of the standard. These subcomittees are:

802.1: Common issues across LANs, such as addressing, management, and bridges.
802.2: Defines LLC and MAC and physical for a specific types of LAN.
802.3:CSMA/CD LANs
802.4:Token Bus LANs
802.5:4 Mbps and 16 Mbps Token Ring LANs.

RFC 1042 specifies how an IP packet is encapsulated in an IEEE 802.x frame as shown below. IEEE 802 shares roughly the same addressing scheme as Ethernet.


Bytes:   6   6   2 |  1    1    1 | 3    2   38-1492   4
      +----+---+---+----+----+----+---+----+--------+------+
      |Dest|Src|Len|DSAP|SSAP|cntl|org|type|  Data  | CRC  |
      +----+---+---+----+----+----+---+----+--------+------+
        802.3 MAC  |   802.2 LLC  |  802.2 |
	                             SNAP

SNAP stands for Subnetwork Access Protocol. DSAP stands for Destination Service Access Point (and is set to 0xAA). SSAP stands for Source Service Access Point (and is set to 0xAA). The cntl field is set to 0x03 and the org code field is set to 0x00. The Type field is set to the same value as used in Ethernet. Notice that the first 14 bytes of Ethernet and IEEE are similar, but the 13th and 14th bytes distinquish the protocols. In fact, Internet hosts must be able to accept both RFC 894 and 1042 frames.

Point-To-Point Protocol (PPP)

Point to point links need a control protocol that can be used to support higher level protocols. PPP is designed to support multiple network protocols and provide option negotiations and other features. RFC 1548 specifies the encapsulation method and Link Control Protocol (LCP) for PPP. RFC 1332 specifies the Network Control Protocol (NCP) for IP. The PPP frame is shown below. PPP is designed to function in synchronous and asynchronous modes.


Bytes:   1    1     1        2    <1500    2    1
      +----+----+-------+--------+------+-----+----+
      |Flag|addr|Control|Protocol| Data | CRC |Flag|
      +----+----+-------+--------+------+-----+----+

The Flag field is set to the special value of 0x7E. This serves to mark the frame boundaries. The addr field is set to 0xFF. The control field is set to 0x03. The Protocol field is set to 0x0021 to signify an IP datagram, 0xC021 to signify link control data, or 0x8021 to signify network control data. The data may be up to 1500 bytes in length.

The flag value of 0x7E must be 'escpaped' if it appears in the data field. Why? no length field. This escaping must also be done for ASCII control sequences. Escpaping is done by using 0x7D to signify the value and then changing the next character by complementing its sixth bit a specific way. This helps to ensure that the escaping does not create a value that would have to be escaped.

The LCP might negotiate to compress the header. This can be done by omitting the address and control fields and shrinking the protocol field to 1 byte. The NCP might negotiate to compress the specific network header used. Dramatic savings can be seen. For example, it is possible to shrink the IP and TCP headers (40 bytes) to 3 or 5 bytes. This can be done by using a table setup and indexing into the table. Also, the NCP can get an IP address dynamically.

Transparent Bridges

Several shared media LAN technologies have to ability to bridge. Bridging is done differently than routing and can be very useful. Bridging can make several small LANs into a single larger LAN transparently to higher level protocols.

The simplest bridge would be a "No Frills" bridge. This bridge functions very simply by listening promiscuously to every packet transmitted and store every packet received until it can be transmitted on the LANs other than the one on which it was received. In other words, just copy each packet to all the other networks. But, the bridge can't change any piece of the frame and this might change the delay characteristics of the LAN. However, bridging can extend the length limit of a LAN. This is done by treating each single LAN as a unit and letting the bridge function independently on each LAN. Thus the bridge controls access on only each LAN.

A smarter method would be to build a "Learning Bridge". Suppose we knew who was on each LAN, the bridge could then only forward frames it knew where needed on other LANs and not forward frames that were not. This turns out to be very easy. It is done like this:

Bridge listens promiscuously to every LAN
For each frame received, the bridge stores the source address in a cache together with the 'port' it was received on. (A port is a physical connection on a LAN).
For each frame received, look through the cache for the destination address. If it is found, forward the frame onto the port in the cache. If it is not found, then forward the frame onto all the ports.
Age each entry in the cache and delete it after a period of time.

Simple and elegant. However, it suffers from a problem. This is OK for trees, but if we have loops, we have problems. Take for example, this topology.


    A-+
      |                 LAN 1
      +---+---+---+----
          |   |   |
          +B1 +B2 +B3
          |   |   |
      ----+---+---+---- LAN 2

What happens when A sends a frame. It doesn't matter to who. The frame loops and generates duplicates. This is very pathological.

One way to fix this is to not allow trees, but that is somewhat undesirable and loops may not be intentional or easy to determine. Bridges have an algorithm designed into them that prunes the topology into a loop-free subset (spanning tree). This algorithm is:

elect a root bridge.
each bridge calculates their distances to the root
for each LAN, elect a designated bridge on that LAN. This is the closest to the root. The designated bridges forward frames from the LAN toward the root.
choose a port ("root port") that gives the best path to the root.
select ports to be in cluded in the tree. These are the root port and any ports on which "self" has been elected designated bridges.

Data traffic is forwarded to and from ports on the tree only. The other ports are not used to forward data.

Asynchronous Transfer Mode (ATM)

ATM is a technology developed by AT&T. It has circuit-switching roots and is being standardized by a consortium called the ATM Forum. ATM is designed for integrated services, such as voice, video, data, etc. and is designed to support Quality-of-Service (QoS). ATM is connection-oriented. A connection is called a virtual circuit(VC). In order to send data, a connection has to be set up before the data may be sent. This action of setting up data also sets up guarantees in the network for resources.

ATM is designed to support various QoS applications. The key to doing this effectively is a layered architecture. An example of the layers involved with ATM for three applications are shown below.


+--------+---------+------------+
|   IP   |  Video  | Higher LLC |
+--------+---------+------------+
|      AAL-5       |    LANE    |
+------------------+------------+
|           ATM                 |
+-------------------------------+
|         Physical              |
+-------------------------------+

AAL stands for ATM Adaptation Layer. This layer involves the packetization into ATM packets, or cells. This layer also involves some control information exchange. The ATM layer is responsible for controlling the sending rate of a source. This is typically done using a leaky bucket scheme. LANE stands for LAN Emulation Layer. It is responsible for allowing higher level LLCs (such as Ethernet or IEEE 802) to run ont top of ATM transparently.

ATM works well by reserving resources in the network. These reservations are not based on 'peak' usage, but on average usage. This gain from peak usage to average usage is called "statistical multiplexing gain".

An ATM cell is 53-bytes in length with 5 bytes of header. The reason behind this length is due to the delay in packetizing voice data and the interactivity that it effects. (48 bytes data X 8 bits)/(64 Kbps) = 6 msec. delay. The ATM cell is shown below.


Bits:   4   8  16    3    1     8      <384
      +---+---+---+----+-----+-----+-----------+
      |GFC|VPI|VCI| PT | CLP | HEC |   Data    | 
      +---+---+---+----+-----+-----+-----------+

GFC: Generic Flow Control. Tells source to adjust rate.
VPI: Virtual Path ID
VCI: Virtual Circuit ID
PT: Payload Type (user or control)
CLP: Cell Loss Priority (can it be dropped or not)
HEC: Header checksum

Routing is based only on VPI, which is a collection of virtual circuits routed together. A connection ID is (VPI,VCI). VC numbering does not have to be unique end-to-end. Just unique on each link. Thus the routing information in the header can be very minimal and can be changed from hop to hop. Below is a good example of how ATM routers hold information.


   1                           1
A---\           C             /---D
     a     1    b1    2      b
      Xc-------aYc---------aZ
     b     2          1      c
B---/                         \---E
   1                           1

In the topology above, we have 3 connections, one from A to C, one from C to D, and one from B to E. The three routers X, Y, and Z have tables that show (port,number) going to (port,number). X has a table with two entries: (a,1)->(c,1) and (b,1)->(c,2). Y has (a,1)->(b,1) and (a,2)->(c,1). Z has (a,1)->(c,1) and (a,2)->(b,1). These entries specify all three connections. So, for the connection from A to C, the X entry of (a,1)->(c,1) is used and for Y the entry (a,1)->(b,1) is used.

53 bytes may seem pretty small for IP fragmentation. It is. So, AAL-5 puts an IP packet over a series of cells to minimize the waste from multiple ATM cell headers.

ATM has a set of QoS attributes. These are: Cell Loss Ratio (CLR), Cell Delay Variation (CDV), Maximum Cell Transfer Delay (MaxCTD), Mean Cell Transfer Delay (MeanCTD), and Minimum Cell Rate (MCR).

Todd L. Montgomery (revised 05.02.1999)