``Data Link Layer for LANs''
Can divide networks into point-to-point and broadcast. Look at broadcast
networks and their protocols.
When many stations compete for a channel (e.g., broadcast
channel such as an Ethernet), an algorithm must arbitrate access to
the shared channel.
Need a way of insuring that when two or more stations wish to
transmit, they all wait until doing so won't interfere with other
transmitters. Broadcast links include LANs, satellites (WAN), etc.
LAN's:
- diameter not more than a few kilometers
- data rate of at least several Mbps.
- complete ownership by a single organization.
MANs cover a city-wide area with LAN technology. For example, cable TV.
Can have higher speed, lower error rate lines with LANs than WANs.
How to allocate the broadcast channel to multiple users (nodes, stations)?
Problem with ALOHA is that frames are blindly sent--bound to be collisions.
Stations listen for a transmission before trying to send data--carrier sense.
Only send if channel is idle.
- 1-Persistent CSMA (Carrier Sense Multiple Access). Sense channel, if
idle then send, if busy wait until idle and then send. 1-persistent
because it sends with probability of one when senses channel is idle.
Collisions?
Effect of propagation delay (takes time for signal to propagate from one
channel to another). Even if zero could have collisions.
- nonpersistent CSMA--less greedy. Sense channel. If idle then send.
If busy then wait random amount of time before repeating the same routine.
Collisions go away? No, can still send at the same time.
- p-persistent CSMA--applies to slotted channels. If channel idle
then send with probability p, with probability q=(1-p), it
defers to the next time slot. Delay for random time if channel busy. Look
at Fig 4-4.
Note: p = 1 implies we transmit immediately, p = .1, we transmit with
probability .1.
The primary advantage of p-persistent protocols is that they reduce
the number of collisions under heavy load. The primary disadvantage
is that they increase the average delay before a station transmits a
frame. Under low loads, the increased delay reduces efficiency.
The following table gives maximum efficiency percentages for some of
the protocols we have studied so far:
Another way to reduce the number of collisions is to abort
collisions as soon as they are detected. CSMA networks with Collision
Detect (CSMA/CD) do just that. How long does it take to detect
collisions:
- at least twice the propagation delay, or
(in worst case, 
for the signal to travel from one end of cable to the other, another
for the collision indication to travel back) - we'll call this interval the contention period
- what does this say about building broadcast networks that span
large distances? (increase propagation delay)
- small frames? (could send entire frame before detecting a
collision)-pad out the frames in the standard
Skip over some protocols.
The IEEE has produced a set of LAN protocols known as the IEEE 802
protocols. These protocols have been adopted by ANSI and ISO:
- 802.2: logical link standard (device driver interface)
- 802.3: CSMA/CD
- 802.4: token bus
- 802.5: token ring
Ethernet is a specific product implementing (or nearly so) the IEEE
standard. Interesting to note that having an Ethernet port on a machine
has become a standard (certainly for workstations).
The 802.3 protocol is described as follows:
- 1-persistent CSMA/CD LAN
- its history is as follows:
- started with ALOHA
- continued at Xerox, where Metcalf & Boggs produced a 3 Mbps LAN version
- Xerox, DEC, and Intel standardized a 10Mbps version
- IEEE standardized a 10Mbps version (with slight differences from
the Xerox standard
- the maximum length of a segment of cable is 500 meters
- segments can be separated by repeaters, devices that
regenerate or ``amplify'' signals (not frames); a single repeater can
join multiple segments
- maximum distance between two stations 2.5 km, maximum number of
repeaters along any path: 4 (why these limits?)
At the Medium Access (MAC) sublayer, frames consist of the following:
- Frames begin with 56-bit preamble consisting of alternating 1s
and 0s. Purpose? Similar to start bit in RS-232-A.
It allows the receiver to detect the start of a frame.
- Start of the frame designated by the byte ``10101011''.
That is, two consecutive 1 bits flag the end of the preamble.
- 48-bit destination address (16-bit for lower speed version).
- 48-bit source address (16-bit for lower speed version).
- 16-bit data length field; maximum data size 1500 bytes.
- 32-bit checksum field. The checksum is a number dependent
on every bit in the frame. The sender computes a checksum and appends
it to the frame. The receiver also recalculates the checksum,
comparing result with value stored in frame. If the two checksums
differ, some of the bits in the frame must have changed and the packet
is discarded as having errors.
There are two types of addresses:
- Unicast addresses start with a high-order bit of 0.
Unicast addresses refer to a single machine, and every Ethernet address
in the world is guaranteed to be unique (e.g., address is sort of like
a serial number).
- Multicast (group) addresses start with a high-order
bit of 1. Multicast addresses refer to a set of one or more stations.
A broadcast address (all 1's) is a special case of multicasting.
All machines process broadcast frames.
The management of multicast addresses (e.g., entering or leaving a
group) must be managed by some outside mechanism (e.g, higher-layer
software).
802.3 LANs use a binary exponential backoff algorithm:
- if a station wished to send a frame, and the channel is idle,
transmission proceeds immediately
- when a collision occurs, sender generates a noise burst to insure that
all stations recognize the condition, and aborts transmission
- after the collision, wait 0 or 1 contention period time before attempting
again (1 contention period time
) - if another collision occurs:
- wait 0, 1, 2, or 3 slot times before attempting transmission again
- in general, wait between 0 and
times, where r is the number of times we've already
retransmitted - finally, freeze interval at 1023 slot times after 10 attempts,
and give up altogether after 16 attempts.
Note: our goal is to keep delays low at low loads, but avoid
collisions under high load.
Also, note that there are no acknowledgements; a sender has no way of
knowing that a frame was successfully delivered.
Can connect hosts to a hub switch. Advantage is that stations use the same
network interface card, but they can run at higher speeds.
Physically a bus, logically a ring with each station having a number.
Use of a special control frame called a token. Can only send a
message by first capturing the token which passes between stations. No
collisions because only one station at a time may hold the token.
Different priority levels at each stations with each getting a fraction of
the amount of time for the station.
Periodically broadcast special tokens to allow new stations to enter the
ring.
Token passed around the ring. It is seized to send a message then
regenerated and passed to the next station.
Non-deterministic nature of CSMA/CD protocol makes real time computing
people nervous.
802.3:
- most widely used of the three
- low delay under light loads
- simple to install and maintain
- analog circuitry required to handle collision detect features
- minimum frame size of 64 bytes is large when
carrying single byte keystrokes
- delay characteristics non-deterministic
- originally limited to 10 Mbps and short distances (using hubs to get
fast ethernet (100Mbps))
- no support for multiple priorities
802.4:
- uses standard analog technology
- more deterministic access time (but not 100% either, due to
ring maintenance overhead)
- supports priorities
- works well under heavy load
- relatively high delay at low loads
- can be mixed with TV and voice equipment
802.5:
- all digital
- can use with fiber optic technology over long distances
- supports both large and small frames
- high efficiency at high loads
- low delays at low loads, bounded delay in any case
- ring monitor is a single point of failure
The Fiber Distributed Data Interface (FDDI) is a standard
for token rings using fiber for individual links:
- supports data rates of 100 Mbps over 200 km
- uses LED rather than lasers (lasers potentially dangerous)
- has a bit error rate of only 1 in
bits - cabling consists of a pair of rings (one for each direction);
two pairs are specified so that the second ring can be used to
reconfigure the ring in the event of a station or link failure
The protocol itself is similar to 802.5, but has the following differences:
- 802.5 requires that the sender receive his frame before
regenerating the token; because of lengths, sender regenerates token
as soon as frame is out its interface, allowing the ring to carry
multiple token/data frames simultaneously
- FDDI can also carry synchronous frames for PCM ir ISDN traffic
Waiting for applications to catch up. Similar to Ethernet which people
said was too complicated when it came out.
On top of MAC layer for DLL equivalent (Fig 4-33).
Service options:
- Unreliable datagram service
- acknowledged datagram service
- reliable connection-oriented service