Home Next: 3. 802.11 Local Area Previous: 1. Introduction: networks, layers

Department of Computer Science

2. The data-link layer


2.1 Functions of data-link layer

The data-link layer, in networking software, is reponsible for transferring data from one machine to another directly connected machine. In other words, the networking layer above will pass it packets of data and the name of a network interface and it must transmit the data. This layer must know how to drive the hardware. In different systems the responsibilities might vary but could include:

In many types of network there is a big variation between how much is done by hardware and how much by software, for example an ethernet card will include lots of the functions, but software must do most of the work of driving a dial-up modem line. These notes will examine the logical problems (not electrical issues) whether the functions are in a software of hardware device driver.

2.2 Topologies

The data-link level software in a computer must send data along different physical networks that its computer is connected to. The topology of a network is its basic architecture, how components are logically connected. The simplest and oldest (and still widely used) is the point-to-point. A system can be build from an arbitrary number of dedicated machine to machine links.

Figure 2.1: Point to point connection

Point-to-point connections like simple serial or parallel lines that join a device on one machine to a device on another, these are commonly used to connect to wide area networks, for example BT leased lines or simple dial-up telephone links. The technology and speed can vary from simple serial lines like RS232 at 9.6 Kbps. to fibre optic cables at 2.5 Gbps. A protocol used on dialup lines PPP. A protocol used for long distance backbone connections is SONET.

The star network, all machines are connected through a dedicated switch:

Figure 2.2: Star topology

These are typically used for local area nets and work at about 150 Mbps or more. Actually they may provide the data-link layer but they share some of the characteristics of the network layer.

The shared bus topology, all machines connect to a common carrier,

Figure 2.3: Multiaccess shared bus topology

Multi-access nets where lots of machines are connected to the same carrier cable (it works a bit like a computer bus). These are the commonest for local area networks. The different types include token rings like FDDI or single lines like Ethernet. Their difference lies in the way they compete for and schedule access to the common carrier between the different machines. There performance is between 10 and 1000m bps. The performance of some ethernets is over 1Gb, these use a similar protocol but they are not really shared bus architectures.

The store-and-forward packet switched network, the switches are high performance purpose built boxes (by CISCO or 3COM or ..), they link with arbitrary toplogies to other switches OR they have ``outside'' links to host computers, or other networks.

Figure 2.4: Store and forward WAN topology

2.2.1 Note on real topologies

The preceding descriptions of topologies are over-simplified logical structures. In reality there are many variations and alternatives, and sometimes a difference between the apparent physical topology and the logical topology of operation of the network. For example:

2.3 Data transmission

The first problem is how are ``bits'' of digital data sent, this is the problem of data transmission. This is an enormous subject that will not be dealt with here. It includes:

Just ignore this for now, but you must know that the topic of data transmission is a major subject in its own right and an area of overlap between the concerns of electrical and electronic engineers and computer scientists. We will only assume that some how ones and zeros can be represented and transmitted.

2.4 Encoding

To send a binary digit along a carrier the sender can vary the voltage or frequency for a fixed period of time, the receiver must detect this change. To do this they must synchronize clocks so the receiver samples at the right time and duration.

The clock is probably a transition from one level to another and triggers the sampling of the line. If the line is at one level to long then the clocks at each end might drift.

There are various forms of encoding:

Figure 2.5: Simple digital encoding

2.5 Error detection

Electrical signals can be corrupted or misread so it is necessary to have a way of detecting any corruption. This is usually done by computing and sending redundant information, the receiver recalculates and checks. The amount of redundant information and how it is calculated affect the likelihood of detecting errors.

2.6 Framing

How are bits of data sent? The receiver needs to know how to interpret the sequence. One bit by itself provides little information, it is necessary to send sequences of bits to represent useful data. The solution is to send data in frames with a given format. The next problem is to know when the sequence, the frame, starts and when it ends, there are three main ways:

With any method that uses an end marker there is a problem that if the value of the end marker character or byte sequence occurs in the data being transmitted then the receiving hardware will believe that the frame has ended prematurely. To solve the problem with byte oriented protocols a technique called byte stuffing is used: a special escape character (DLE in ASCII) is used. Whenever the end marker value occurs in the data it is replaced by the escape character followed by a code indicating that the end marker was replaced. When the receiver detects the escape it removes it and the following character and replaces it with the original code required. (If the value of the escape occurs in the input then it will be replaced by some other escape sequence. NB this is just like the use, in C, of the \ escape character, where \n is a newline \\ is \ etc.)

Things are simpler with bit oriented protocols, they use bit stuffing. The sender, to avoid the termination sequence, for example 01111110, being sent in the data, will if five ones occur (11111) just stick in an extra 0. The receiver will be given the data and will remove any zero that occurs after five ones. It is now OK because the start and end markers are the only things that will have six ones.

2.7 Reliable transmission

Depending on the networking system being used, it might be important for the data-link layer to be reliable (not in the TCP context, but maybe others). The simplest solution is to used an acknowledgement, timeout and retransmit system. This is done in the HDLC protocol. It will not be described here because it is dealt with in chapter 6 on TCP.

2.8 Local area networks including ethernet

There have been many forms of local area network architecture: token ring, FDDI, ATM, ethernet and now wireless networks. However the one used most widely is ethernet (and increasingly wireless).

2.8.1 Standards

The IEEE, American Institute of Electrical and Electronic Engineers, has many standards that have become international standards, (the ``Unix'' standard called POSIX is an IEEE standard). IEEE have a set of standards called 802 that cover many aspects of local area networks (and some wider network issues):

802.2 logical link layer, interface to layers above
802.3 CSMA/CD, the ethernet family, many sub-standards
802.3u 100Mbps ethernet
802.3z 1000Mbps ethernet
802.5 token ring network
802.11 wireless LAN
802.11x 802.11a, 802.11b, 802.11g etc. different wireless frequencies
in the 802 family there is an important distinction between: This distinction is used in the 802.11 wireless protocol, the network layer (usually IP) communicates with the LLC layer which then passes LLC frames down to the 802.11 MAC layer. However this distinction is not made by ethernet (802.3) because its design pre-dates the introduction of 802.2. So ethernet packets do not encapsulate or contain LLC packets, higher levels (like IP) interact directly with 802.3 not with 802.2.
Figure 2.7: IEEE 802 protocol stack

2.8.2 802.3 (ethernet) features

Ethernet is a form of carrier sense multi-access network with collision detection or CSMA/CD, ``Ethernet'' was a brand name belonging to Xerox but it is so common it is nearly always used as the name instead of CSMA/CD.

Since many machines can connect to the same Ethernet cable they have to use source and destination addressing. The address is 48 bits long and is built into each Ethernet card or device when it is manufactured and is assumed to be unique. An Ethernet packet contains a preamble which is a standard recognisable sequence of bits so that devices detect the start of a packet, the destination and source addresses, a field identifying the protocol of the message in the data, ie. IP or something else, so it can be passed to the right layer above.

Figure 2.8: Ethernet packet format (sizes in bytes)

2.8.3 Ethernet operation

Another problem arising from having lots of machines on the same cable is synchronising the use of it, when one device puts a packet on the cable no other machine can. In other words ``collisions'' can occur and must be dealt with. The operation of sending is as follows:

  1. if the carrier is busy (ie. some other computer is sending) then wait, or,
  2. if the carrier is idle then start sending bits,
  3. while sending, monitor the carrier to see if any other bits appear, if not then done.
  4. otherwise there is a collision, some other device transmitted at the same time; if so stop, put error bits on the carrier (jamming signal) so all other devices know there is an error and then wait a variable time before going to step 1. The length of delay is random and increases with repeated collisions, it is called exponential back-off.

Ethernets are very successful and very widely used but they perform very badly if they get much more the half their load. This is because the rate of collisions rises exponentially as the load increases, and also the consequent increase in re-transmissions.

2.8.4 Ethernet cable length

The method depends on a host being able to detect the collision before it stops sending, otherwise a collision might have occurred at the receiver but the sender will not realise and not re-transmit. Consequently there is a maximum length for a 10Mbps ethernet network of 2500m and a minimum length of frame of 512 bits (64 bytes). Assume the worst case:

The time, d, taken for a bit to travel 2500m is 25.6 micro-secs, so the first sender must be still be sending after 2*d, 51.2 micro-seconds, On a 10Mbps ethernet 512 bits are transmitted in 51.2 micro-seconds so in order to still be sending and detect the collision the minimum packet length must be 512 bits.

This problem still applies for 100Mbps and 1000Mbps ethernets, they have maximum cable and minimum packet size limits. They also use additional ways to detect collisions, but the basic problem is the same. So the 100Mbps system using hubs and switches and running 10 times faster can either have a minimum frame length of 5120 bits or a maximum length of 250m, it shortened the maximum length.

2.8.5 Ethernet bridges

A bridge is a way of joining two or more ethernets. It appears to the connected hosts that there is only one network, they address, transmit and receive data in the same way, it doesn't affect them if the receiver is on the same or the other side of the bridge. The bridge works by receiving all packets from all networks, buffering them and passing them on to the other networks. This has the very important consequence that the combined networks can be more than 2500m. This is because the bridge deals with the carrier sense, collision detection and, if necessary, re-transmission on the other ethernets.

Figure 2.9: Ethernet bridge

So if host A on ethernet 1 sends a packet to host F using F's address it will be intercepted by the bridge b1-2 (because it grabs everything), retransmitted unchanged by the bridge on ethernet 2, and finally get to F.

Most bridges are adaptive learning bridges. Their basic operation is the same but they also record all the sender addresses of all the packets sent on each ethernet, this way they learn which ethernet each host is attached to. Then, when the must pass on a packet, they examine the destination address and only forward it to the network that the destination host is on. So if host C sends to host A it will be intercepted by the bridge but it will not be forwarded on network 2 because the bridge has learnt that host A is on network 1.

2.8.6 Ethernet physical topologies

The basic original topology of the 10Mbps ethernet was the shared bus structure, a coaxial cable, to which every host is attached, see figure 2.10.

Figure 2.10: Original ethernet topology

The 100Mbps uses UTP (twisted pair) cables that plug into a a box, either a hub or a switch. The hubs or switches can be connected together in a hierarchy or using 10Mbps links, see figure 2.11.

Figure 2.11: Ethernet hub

this looks like a star network topology, it is physically but not logically. Logically and functionally it is still a shared bus. When one host sends a packet it goes to all the other hosts.

Figure 2.12: Inside an ethernet hub

Notice, in figure 2.12, that the link goes up the twisted pair, into the hub, back down one link in the next twisted pair and back to the hub again. In other words it works exactly like the shared bus. Hubs can have between 4 and 64 ports.

With a hub there is still contention, while one host is using the hub no other host can. By spending a bit more money you can get a switch. A switch looks like a hub but internally it is totally different. A switch still appears the same as any ethernet to the host but it is almost as every host is on its own separate ethernet with bridging between them, see figure 2.13.

Figure 2.13: An ethernet switch

So if host 1 is sending to host 3 the packets go through a type of internal adaptive bridge b1-3 and because b1-2 and b1-4 are adaptive they will not forward the packet. This means that host 2 can communicate with host 4 at the same time without collisions.

Home Next: 3. 802.11 Local Area Previous: 1. Introduction: networks, layers
Page generated: 2006-12-22 by Bob Dickerson

© University of Hertfordshire Higher Education Corporation