Data Link Layer, featuring 802.x
Overview
· alternately called link layer or datalink layer
· between network and physical layer
· partitioned into two sublayers:
o logic link control (LLC) technology-independent “upper” sublayer
o media access control (MAC) technology-dependent “lower” sublayer
· focus on communication between 2 directly connected nodes
· PDU is frame
· Major services/issues:
o Framing
o Channel access
o reliable delivery
o flow control
o error detection and possibly correction
· Note that few of these services is exclusive to this layer!
· Why would similar services be provided at multiple layers?
· Most datalink protocols implemented in hardware
· Host device is Network Interface Card (NIC), aka network adaptor
· Network extending devices include: repeaters, hubs, switches, bridges
· Focus on IEEE 802.x standards for local area networks (LAN)
· signal errors occur as result of interference, attenuation, etc
· addressed at several OSI layers (one of its criticisms)
· concentrate on data link layer here
· error at data link level: 1 bit received as 0, or vice versa
· consider error pattern:
· single bit : one bit in data unit (e.g. byte, frame)
· burst : multiple consecutive bits in data unit
· multiple bit : multiple non-consecutive bits in data unit
· major strategy: redundancy
Vertical Redundancy
Check
· a.k.a. parity check, append a parity bit to data unit
· even parity: set parity bit so that total # of 1’s in unit (including itself) is even.
· odd parity : similar
· detects all errors where number of erroneous bits in unit is odd (1,3,5)
· cannot detect even numbers of errors (parity will remain correct)
Longitudinal Redundancy Check
· 2-dimensional parity check
· parity check over a block of consecutive data units
· each data unit contains VRC parity bit
· append data unit containing parity bit for corresponding bit position across all data units in block
· cannot detect even numbers of errors in corresponding positions of even numbers of data units. (e.g. units 2 and 4 both have errors in bit positions 5 and 7).
Concerning the terms vertical and
longitudinal:
Origins are magnetic tape era. Vertical refers to data stored across the width of the tape (e.g. a byte); longitudinal refers to information stored along its length. Reference: Introduction to Data Communications, by Larry Hughes, Jones and Bartlett, 1997, page 145.
Cyclic Redundancy Check (CRC)
· CRC bits are appended.
· CRC value is such that combination of data and CRC bits form value divisible by “well-known” divisor (the generator polynomial).
· if receiver gets non-zero remainder, error occurred.
· uses modulo-2 division, subtraction, and addition
· CRC generator:
· start with original data M, r-degree generator polynomial G.
· append r 0’s to data, result is M'.
· divide M' by G, yielding quotient Q and remainder R.
· add R to M', yielding T.
·
transmit T.
· CRC check:
· start with received data T+E, generator polynomial G.
· divide T+E by G, yielding quotient Q and remainder R
· if R is 0 then E is 0. truncate the last r bits of T and pass on.
·
if R is not 0, then E is not 0. An error has occurred.
· polynomial representation
· divisor bit string usually expressed as polynomial on x
· exponent represents bit position and coefficient is bit value (0 or 1).
·
example: string 100101 represented as x5+x2+1.
· there are standard generator polynomials
· CRC-16 : x16+x15+x2+1 (17 bit generator, yields 16 bit CRC)
· CRC-ITU : x16+x12+x5+1
· CRC-32 : (33 bit poly with many terms)
· probabily of undetected error is quite small.
· Normally implemented in hardware using shift registers and XOR-gates with feedback. CRC-ITU is 10001000000100001. Corresponds to set of shift registers having 4, 7 and 5 bits, respectively
Error Correction
· Hamming distance
· given encoding, minimum # bits that must be flipped to change one valid code into another valid code.
· Example: Hamming distance for ASCII is 1.
· Example: encoding 1001, 0011, 1100, 0110, 1010, 0101, 0000, 1111 has distance 2 and can encode 8 values.
· n-bit errors can be detected if Hamming distance is n+1
·
n-bit errors can be corrected if Hamming distance is
2n+1
· Hamming code (1950)
· allows receiver to determine which bit was flipped.
· redundancy bits placed in specific bit positions; each represents VRC over specific bit positions
· assume bit positions numbered starting with 1. Bit positions of redundancy bits are powers of 2 (1,2,4,8,etc). Redundancy bit in position i represents VRC over bit positions whose binary representation has 1 in its bit position i!
· Example: redundancy bit in position 1 is VRC for all odd-numbered bit positions: 1,3,5,7, etc (binary representation has 1 in position 1). Redundancy bit in position 3 is VRC for bit positions 4,5,6,7 (binary representation has 1 in position 3). Note the overlaps.
· number of redundant bits r required for unit of m data bits determined by smallest r such that 2r >= m + r + 1
Frequency Division Multiple Access (FDMA) – a.k.a. FDM, highlighted in course Introduction
Time Division MultipleAccess (TDMA) – a.k.a. TDM, highlighted in course Introduction
Code Division Multiple Access (CDMA)
ALOHA
Slotted ALOHA
Carrier Sense Multiple Access (CSMA)
CSMA with Collision Detection (CSMA/CD)
Polling protocols
Token-passing protocols
Address Resolution Protocol (ARP)
IP addresses are logical, not physical(to achieve uniformity in heterogeneous internetwork).
Physical transmission, however, requires physical addresses. There are several methods for transforming (resolving) the IP address into the correct physical address at each hop!
ARP is Address Resolution Protocol. It occurs in TCP/IP network interface layer. Higher layers use IP addresses exclusively, lower layer uses physical address exclusively.
Physical address good only within network. When IP packet crosses networks (at router), ARP must be applied by router to get hardware address for next hop (ARP must also be applied by sending host, to get the packet to its first router).
Methods used by TCP/IP fall into three categories:
1. Table lookup. Each entry of mapping table contains: IP Address / Physical Address pair. Note: since physical addresses are good only within a network, all table entries have same IP prefix. Methods utilized to speed the lookup : hashing, or direct indexing (a hashing method in which IP suffix is used as table index -- not good if wide suffix gaps). Used by WANs.
2. Closed-form computation. Apply mathematical function to IP Address to resolve physical address. Possible on networks that use configurable addressing (NIC hardware address can be assigned at bootup or dynamically). Since both logical and physical address are controlled by network software, the logical address can be chosen to be an easy function of physical address (or vice versa). E.g. hw address == IP suffix. Used by configurable networks.
3. Message Exchange. Resolver broadcasts address-request message containing IP address to network. Machine with matching IP address generates response containing its hardware address. Alternatively, put address-resolution server on network and send all such requests to it. It must also have protocol for keeping address information up-to-date. Used by LANs (esp. ethernet).
ARP is TCP/IP protocol standard for address resolution via broadcast MAC message exchange on LAN. Primary use is IP-ethernet resolution. Aspects are:
1. Message exchange protocol: Two message types: request and response. Requester broadcasts request; node whose IP address matches request generates response directly to requester (other nodes ignore request after verifying they are not target).
2. Message format: same for both requests and responses, and general enough to handle different address sizes. Here is IP-ethernet example (addresses are 4 and 6 bytes, respectively):
|
FIELD |
LENGTH IN BYTES |
|
Hardware Address Type |
2 |
|
Protocol Address Type |
2 |
|
Hardware Address Length |
1 |
|
Protocol Address Length |
1 |
|
Operation (request,response) |
2 |
|
Sender Hardware Address |
6 |
|
Sender Protocol Address |
4 |
|
Target Hardware Address |
6 |
|
Target Protocol Address |
4 |
3. Message fits in single frame. Frame-type field in frame header identifies payload as ARP message (ethernet code: hex 806).
4. Sender algorithm, given IP address.
a. Check cache of ARP bindings (internal table). If binding found there, address is resolved.
b. Else broadcast ARP request message with your protocol (IP) and hardware address, and target protocol address.
c. When ARP response received, extract target hardware address. Address is resolved. Also put address pair into ARP cache.
5. Receiver algorithm.
a. Upon receipt of ARP request, see if Target Protocol Address matches yours. If not, ignore.
b. Else prepare and transmit ARP response. Requester's hardware address was in request, so that becomes destination address for frame.
c. After transmitting ARP response, store requester's protocol-hardware address pair in ARP cache. Request means that it has something to send your application layer, so you probably will be generating a response soon and will need its address.
Protocol to handle the reverse translation: ethernet to IP.
Host uses it to learn its own IP address. When might this be necessary?
Useful for diskless workstations, or when booting a computer.
Sends appropriate request frame and receives response from a station that knows.
IEEE 802 project
· Collection of LAN standards
· Major sections are:
· 802.1 : internetworking standards (network layer)
· 802.2 : LLC specifications
· 802.3 : Ethernet specifications
· 802.4 : Token Bus specifications
· 802.5 : Token Ring specifications
· 802.11 : wireless LANs
· Independent of LAN technology used
· Frame structure based on HDLC (High level Data Link Control)
· HDLC is reference model for bit-oriented frame structures.
· LLC frame structure
1. DSAP (destination service access point)
2. SSAP (source service access point)
3. Control field (frame type)
4. Information field
· Does not contain HDLC fields for flags, station address, CRC
· LLC frame is contained within data field of LAN frame
Overview
· Originally developed at Xerox by Bob Metcalfe.
· Named after the “ether”, a term describing the medium through which scientists once thought electromagnetic radiation flowed.
· Ether refers to the cable. Typical wire is 10Base-T (twisted pair), 10Base-2 (thin coax), 10Base-5 (thick coax). 10 refers to Mbps.
· Uses digital signal (+.85v, -.85v, 0v for idle), with Manchester encoding: each bit has a signal transition (low-to-high or high-to-low) in middle, to facilitate synch. This is Baseband.
· Transmission rate 10Mbps; Fast Ethernet is 100Mbps.
· Characterized by bus topology and CSMA/CD for coordinating transmission.
Frames Collide on the
Common bus
Consider how collisions can occur, since a station will not begin transmitting until it senses an idle carrier.
If collision occurs, how to avoid repeating it, since both stations will try again? Solution is to have each station wait a random amount of time before retrying. The two stations will likely select a different random value.
Specific Ethernet solution:
a. Specify fixed time slot (512 bits or 51.2 microseconds at 10Mbps)
b. station can begin transmitting only at beginning of time slot
c. after i’th collision involving a frame, station waits between 0 and 2i-1 time slots, selected randomly, before trying again. called Binary Exponential Backoff.
NOTE: B.E.B. is compromise solution to conflicting situation:
if range of time slots too small, high probability of repeated collide
if range of time slots too large, throughput suffers (wait too long to retransmit)
Ethernet Frames
Ethernet uses 48-bit (6 byte) addresses. Each frame contains both source and destination address.
Recall that frames are broadcast.
· NIC reads destination address as frame comes by.
· If it matches the NIC i.d. number, the frame is saved and passed on to the O.S. of its station.
· Otherwise, remainder of frame is ignored. Destination address is at the beginning of the frame. NIC handles all this without bothering its attached station.
Some frames are truly
broadcast, e.g. intended for all stations.
A special destination address, usually all 1’s, is reserved for this purpose,
and all NIC cards will match it.
Frame Format
Generic: consists of frame header part, with addressing and type information, and frame data part with the bits/bytes being transmitted.
|
field |
bytes |
description |
|
preamble |
8 |
alternating 1 and 0 for synch (Manchester sine wave) |
|
destination |
6 |
all 1’s means broadcast, first bit 1 = group address, else individual |
|
source |
6 |
physical address of source station |
|
type/length |
2 |
#data bytes, or predefined frame type (mutually exclusive ranges) |
|
data |
46-1500 |
If less than 46 bytes of data, is padded out to 46 bytes with zeroes. Necessary for minimum 512 bit frame length (relate to time slot) |
|
CRC |
4 |
Cyclic Redundancy Code |
Ethernet Cabling Nomenclature
Links courtesy of Purdue University web site for textbook: Computer Networks and Internets, by Douglas Comer.
NIC. Network Interface Card. Interface between computer and network. Handles network transmission so that the main CPU need not bother. Consider it a peripheral, like a disk or CD-ROM. Better reasons for NIC:
1. general purpose CPU is not fast enough to handle network speed traffic
2. CPU speeds vary from one computer to the next, whereas network operates at fixed speed
3. OS scheduling policies cannot guarantee the real-time response that network traffic processing requires
Thicknet. Uses thick coaxial cable. (.5” O.D. – aka 10Base5 – 500 meters max betwen repeaters). AUI (Attachment Unit Interface) cable connects NIC to transceiver, which is how it attaches to the bus. Connector at NIC and transceiver end called AUI connector. This is the original ethernet technology. Can connect multiple stations to one transceiver using a connection multiplexer.
Thinnet. Uses thin coaxial cable(.25” O.D. – aka 10Base2 – 200 meters max between repeaters). Tranceivers not required (functionality built into NIC). NIC attaches to cable using BNC connector. Typically attach BNC T-connector to NIC, so that cable (the bus) can run directly from one computer to the next. NIC with AUI can be connected to thinnet cable using adapter/transceiver.
10Base-T. Uses twisted-pair cable. NIC attaches to cable using RJ-45 connector (like telephone). Stations are connected to hub via the twisted pair. Hub has fixed capacity (e.g. 32 stations). Physically, the topology resembles a star, but logically it is still a bus – all stations receive all network traffic. Older NICs can be attached using an adapter.
IEEE 802.4 : Token
Bus
· Not as popular as ethernet and token ring.
· A token is like a potty pass. The network only has one, and no station can transmit until it possesses the token. If token passes by and the station is ready to transmit, it grabs the token, transmits, then releases the token.
· Developed at GM for factory automation (real-time). Emphasis on:
· Token: guaranteed limit on delay, thus token with priorities. can't risk ethernet.
· Bus: minimize damage of cut cable, thus bus rather than ring.
· Coax cabling, with analog signalling using amplitude + phase modulation.
· Basically, broadcast token on the bus, and devise elaborate protocols to assure integrity of token and network, and prioritized delivery.
·
Logical topology is ring! Stations are sequenced, and
each station knows sequence number of its two neighbors. Protocols are very
complex.
IEEE 802.5 : Token Ring
Overview
· Originally developed at IBM.
· A token is something like a “potty pass”, used to prevent collisions.
· Typically wired with twisted pair.
· Digital signal with differential Manchester encoding.
· Transmission rate is 4Mbps or 16Mbps.
· Characterized by a ring topology. Ring is unidirectional.
· signal comes into NIC, which regenerates and transmits. When NIC powered down, switch closes so signal can pass thru
Physical Configuration may be Star
· Sometimes configured like a star with a special hub (MAU: multistation Access Unit), to mitigate problem of cut cable :
· imagine pulling the cables between each pair of stations into the center of the ring and running them through a hub.
· If a cable is cut, the hub can sense this and close a by-pass switch that isolates the connected station.
· This allows the remaining ring to function.
The token
· Token is special bit pattern (3 bytes long) that circulates on idle ring.
· Collisions cannot occur because station must have possession of token to proceed.
Frame transmission proceeds thusly
1. Sender reads token on ring and removes it.
2. Sender transmits frame onto ring. For 16Mbps ring, token is released after the frame (early release).
3. Transmitted frame circulates around the ring.
4. Receiver copies bits into buffer but regenerates frame on ring. It sets ACK bits in last byte.
5. All other stations just regenerate frame on ring.
6. As bits come back to sender, they are “drained” from ring. Error-check here.
7. For 4Mbps ring, sender releases new token when step 4 completed. (for 16Mbps, see step 2)
Consider performance of this protocol on heavily loaded ring (many stations want to transmit).
Is the protocol fair? The protocol also includes priorities.
|
field |
bytes |
description |
|
start delimiter |
1 |
invalid manchester signal (no transition) |
|
access control |
1 |
token bit plus priority bits plus reservation bits |
|
end delimiter |
1 |
invalid manchester signal |
|
field |
bytes |
description |
|
start delimiter |
1 |
same as above |
|
access control |
1 |
same as above |
|
frame control |
1 |
frame type (distinguish data from from ring maintenance frame) |
|
destination |
6 |
all 1’s for broadcast, first bit 1 for group, else individual |
|
source |
6 |
source address |
|
data |
0-4500 |
limited by amount of time station can hold token |
|
checksum |
4 |
CRC-32 checksum |
|
end delimiter |
1 |
same as above |
|
frame status |
1 |
ACKnowlegement that receiver can send as it forwards frame |
Priorities
· Both token and data frame have 1-byte access control field.
· Higher priority station may reserve token by placing its priority into access control byte
· Transmission is FCFS among waiting stations with highest priority
Ring Monitor keeps network under control
· Designated monitor station plus backup
· Regenerates token if none seen before timeout
· Removes frame seen for second time (sets frame status bits first time around)
ISO 9314 : FDDI
·
Fiber Data Distributed
Interface
·
FDDI is not
part of IEEE 802.
·
Token ring based on fiber optic cabling. Transmisson
rate is 100Mbps.
·
Fiber is unidirectional; stations connected by pair of
fibers transmitting in opposite directions. "inner ring" normally not
used. In case of cut or station failure, stations on either side close a switch
connecting the pair: loops back to re-form the ring!
·
Transmission protocol similar to token ring. Uses
"early token release"; token is released as soon as last bit
transmitted -- doesn't wait until last bit drained. Why? To achieve higher
fiber utilization -- if error occurs (highly-unlikely on fiber), re-transmit on
next go-around.
·
frame format nearly identical to token ring
·
uses NRZ-I, 4-out-of-5 digital signal. Each 4 bit combination has 5 bit encoding
having maximum 2 consecutive 0 bits (synch aid). Leaves some 5-bit codes available for control use.
· Designed as 10baseT repeater: regenerates and retransmits input signals
· Physical layer device.
· a.k.a. concentrators
· Muliple ethernet stations plug into one hub to form star.
· Unless buffers provided, all stations must use same transmission protocols (e.g. 10Mbps)
· Hubs can also be connected to each other, to form trees
· Advantage of hub and tree configured hubs is: they extend LAN distance
· All stations connected through hub(s) comprise a collision domain, a.k.a. segment
· There is limit on hub usage: use 10baseT as an example
o no more than 4 hubs between any pair of stations
o maximum 100 meters before regeneration
o therefore, max 500 meters between any pair of stations (5 hops @ 100 meters each).
· 10baseT allows up to 1024 stations on a segment, but all are in same collision domain so overall throughput limited to 10Mbps.
· Datalink layer device
· Can use to connect two ethernet segments of same type
· Can use to connect two ethernet segments of different type (e.g. 10Mbps and 100Mbps)
· Can use to connect two dissimilar LANs, e.g. a token ring to an ethernet.
· Capable of forwarding and filtering frames
· Filtering protocols have effect of routing w/i a LAN
· Such bridges sometimes called routers, but we reserve that term for network layer device
· Filtering is based on bridge table (analogous to routing table). Each entry contains:
o station physical address
o output port (interface) to get toward it
o timestamp for aging
· When frame received at bridge:
o Look up destination address in bridge table
o If not found, flood (output on all port).
o If found and output port == input port, discard frame. This is filtering (source and destination are on same segment).
o If found and output port != input port, forward.
· Bridge table built and maintained dynamically (adaptive or learning or transparent bridge)
· How to learn which output port for which destination station?
· Backward learning: note source address of incoming frame and port that it came from, and conclude that frames having that station as destination should be forwarded on same port.
· Problem: if bridge topology forms loops, the early flooding can cause frames from one source to arrive on multiple input ports. Frames can loop and replicate exponentially.
· Note: it is desireable for bridge topology to form loops, for network resiliency (more than one possible route, in case a segment goes down).
· Ethernet solution: bridges engage in control protocol to construct routes which do not form loops, called spanning trees (covers all network segments but contains no loops)
· Spanning tree advantage: no loops. Disadvantage: heavy traffic around root, some links unused.
· Token ring solution: Force the source station to specify the route! Called source routing. Station learns route through protocol that broadcasts discovery frame for desired destination. Every bridge forwards it, and when reply frame comes back from destination, each bridge appends its own ID. When reply frames get back to source station, each contains a route. Source station selects the best one and uses it in the future.
· A bridge device for interconnecting Ethernet segments
· Has input buffers, output buffers, switching fabric
· Note: buffer space can be centralized, then dynamically alloc/dealloc for each port
· Ideal for connecting heterogeneous segments (e.g. 10Mbps, 100Mbps, 1000Mbps)
· Much more expensive than hub, but each port represents different collision domain
· Cost depends on # and combination of ports
· Can switch multiple transmissions at once, if each destination is different segment.
· Normally store-and-forward, can also get cut-through.
· Cut-through will begin output as soon as output port determined, if it is idle
ATM basics
·
concept: simple and fast
·
data rate: 155 Mbps and 622 Mbps
·
packet-switched
·
fixed size 53-byte packet
called cell
·
small promotes multiplexing
with good response to all
·
fixed size facilitates
switching (many functions in HW: faster)
·
connection-oriented service
(virtual circuit)
·
sequence guaranteed
·
cell delivery not guaranteed!
·
Single-bit error correction
instead of retransmission (OK for fiber)
·
Usable for either LAN or WAN
·
Defines OSI layers 1-4
(physical - transport) only
ATM is underlying technology for B-ISDN
Broadband-ISDN for very high speed
services
Proposed B-ISDN services include:
a.
video on demand
b.
CD-quality audio
c.
multi-media e-mail
d.
LAN interconnections
e.
high speed data transmission
Layered network architecture
a. physical layer
·
PMD sublayer
·
Physical Medium Dependent
·
volts, bit timing, etc.
·
OSI layer 1
·
TC sublayer
·
Transmission Convergence
·
checksums, framing
·
OSI layer 2
b. ATM layer
·
cell layout, header fields
·
virtual circuit management
(routing, switching)
·
OSI layer 2/3
c. ATM adaptation layer (AAL)
·
interface to applications (to
be carrier for many different applications)
·
At least 4 service levels
have been defined:
·
AAL1 : constant bit rates
(CBR service, such as video)
·
AAL2 : variable bit rates
(VBR service)
·
AAL3/4 :
connection-oriented/connectionless (ABR, available bit rates)
·
AAL5 : sequencing and error
control (UBR, unspecified bit rate, example IP)
·
SAR sublayer
·
Segment And Reassembly
·
provides variable-length
packets (convert variable / fixed)
·
CS sublayer
·
Convergence Sublayer
·
provide various packet
services (packetizing, adding headers)
ATM links
·
category 5 twisted pair good for 100 meters
·
fiber good for several kilometers
·
all links are point-to-point
·
host to switch
·
switch to switch
·
unidirectional, cable pairs
ATM Switches
·
cells arrive asynchronously
on input lines
·
arrive at each switching
cycle
·
cells accepted into
“switching fabric”
·
cells may require several
switching cycles to switch
(switch looks in routing table to match cell’s virtual circuit number)
·
discard cell only in
emergency
·
never reorder cells from
given virtual circuit
Cell format
·
53 bytes fixed total length :
48 data, 5 header
·
Header format
·
12 bit VPI
·
Virtual Path Id
·
16 bit VCI
·
Virtual Channel Id
·
Identifies channel within a specified path
·
3 bit PT
·
Payload Type
·
1 bit CLP
·
Cell Loss Priority (0==high,
1==low)
·
if 0, switch cannot discard
cell if cells with CLP==1 remain
·
8 bit HEC
·
Header Error Control (CRC
applied to first 4 bytes of header)
·
corrects single bit errors
(most common on fiber) and some multibit
Routing
·
host-to-switch routing uses
VPI and VCI (on both ends)
·
switch-to-switch routing may use VPI only!
·
no standard, switch designers
determine
·
no fixed routing algorithm
·
advantage of using VPI only:
small tables
·
VPI value is relative to a
switch!
·
can can change at each hop!
·
Each routing table has two
VPI: incoming-VPI and outgoing-VPI
·
Switch matches cell VPI to
incoming-VPI for routing table lookup
·
Switch changes cell VPI to
corresponding outgoing-VPI
·
Allows VPI to be short (need
IDs only for neighbor switches, not global)
·
If VCI not used in routing,
all channels from same path go same route
·
ATM is virtual circuit, so
route setup once per connect
[notes
| CSC 465 | Peter
Sanderson | Computer Science | SMSU ]