Link Layer Flashcards
What are the 4 link layer services?
- framing
- synchronisation
- flow control
- errors in transmission
How does framing work in the link layer?
- encapsulates datagram into frame
- adds header and trailer
What are MAC addresses and what are they used for?
- used if shared medium
- used in frame headers to identify source and destination
How does the link layer use reliable delivery between adjacent nodes?
- seldom used on low bit-error link
- half/full duplex
Do wireless links have high or low error rates?
high
How are link layer functions implemented?
- in an adaptor (network interference chip NIC)
- on a chip
What are the two types of links?
- point-to-point
- broadcast
What are the 3 classes of MAC protocols?
- Channel Partitioning
- Random Access
- Round robin
How does channel partitioning work?
allocate to node exclusively
How does random access work?
contention mechanisms
How does round robin work?
Nodes take turns
How does point-to-point data link control work?
- 1 sender
- 1 receiver
- 1 link
- no MAC
What are the 2 most popular DLC protocols?
- PPP: point-to-point protocol
- HDLC: high level data link control
How is a PPP data frame structured, what does each part do and how many bytes for each section?
8 - Flag: delimiter
8 - Address: nothing
8 - Control: nothing
8/16 - Protocol: upper layer protocol to which
frame delivered
Variable: Info: upper layer data being carried
16/64 - Check: cycle redundancy check for error
detection
8 - Flag
What are the 3 performance considerations for the link layer?
- Delay between ready to transmit and completion of successful transmission
- Throughput - total rate of data being transmitted between stations
- Utilisation of the medium - fraction of total capacity being used
What is propagation delay?
time taken for signal to propagate from one node to the next
What is transmission delay
time taken for transmission to send out block of data
What is the equation for propagation delay?
distance / velocity
What is the equation for transmission delay?
Length of frame / data rate
What is an example if a centralised round-robin technique?
Polling
What is an example of a distributed round-robin technique?
Token Bus
Token Ring
What is an example of a centralised reservation technique?
Centralised reservation
What is an example of a distributed reservation technique?
Distributed reservation
What is an example of a centralised contention technique?
There are none
What is an example of a distributed contention technique?
ALOHA, CSMA, CSMA/CD
What is polling?
Master node invited slave nodes to transmit in turn
What is token passing?
Control token is passed form one node to the next sequentially
What is a random access MAC protocol specify?
- how to detect collisions
- how to recover from collisions
What are examples of a random access MAC protocol?
CSMA, CSMA-CD, CSMA-CA, ALOHA, slotted ALOHA
What is CSMA?
- carrier sense multiple access
- LAN protocol
- if channel is busy then wait until becomes idle
- if collision occurs wait a random time and start over
What are the 6 CSMA-CD performance assumptions?
- N independent stations
- only 1 medium channel
- Normalised transmission time (=1)
- if overlapping -> collision -> frame loss (only source of error)
- continuous or slotted time
- carrier sense or no carrier sense
For 1 persistent CSMA-CD what is the probability that exactly one station attempts transmission in a slot?
A = NP(1-P)^(N-1)
N = no of stations
P = prob station transmits during an available slot
Slot = twice the end to end propagation = 2a
What is the utilisation for 1 persistent CSMA-CD?
U = 1/[(1+2a)/A]
What does a bus ethernet cable have?
coaxial cable
What does a star ethernet cable have?
switch
What is the ethernet frame structure?
Preamble
Destination address
Source address
Type
Data
CRC
What is a token ring?
- point to point interfaces
- token circulates round ring
- seize token ot transmit
What are the token ring states?
- listen
- transmit
When is the token released on a token ring?
after the station finishes transmitting and the receipt of the physical transmission edge
What are the performance assumptions for the token ring?
- normalised throughput to
system capacity - normalised transmission time
- propagation delay = a
- N stations ready to transmit
- all stations equidistant
If a>1 what time is the transmission finished for a token ring?
t0+1
if a>1 what time does all the the frame return back to the start for a token ring?
t0+1+a
If a<1 for a token ring, what is the transmission process?
- frame started to be sent
- still transmitting when the
frame starts to be received - waits for all of frame to be
received until sending ack
What is the token ring utilisation for a<1?
U = 1/(1+a/N)
What is the token ring utilisation for a>1?
U = 1/(a+a/N)
For a broadcast token ring mechanism, what is the transmission process?
- if have data, listen
- free token then append data
- transmit token
- information goes round ring
- one station reads the data
- full frame transmitted back
round to start - station assumes data read
and extracts data back - token free again
What are the 2 flow control protocols?
stop and wait
sliding window
What are the 3 error control protocols?
stop and wait ARQ
selective reject ARQ
go back n ARQ
What is the purpose of flow control?
assure sender doesn’t overwhelm receiver
What is the principle of flow control?
do not accept frames from sender until receiver grants permission
What is the half duplex stop and wait protocol?
- send frame
- receives ok
- acknowledge
- send new frame
What is the utilisation of the stop and wait protocol for a half duplex?
U = 1/(1+2a)
What is the sliding window protocol?
- sender keeps list of
sequence number of frames
sent - keep frames in memory until
ack - if buffer full, stop transmitting
- receievr keeps window size
with number of frame
sequence - frames falling out of window
discarded
What is the utilisation of the sliding window protocol?
U = W/(2a+1)
What is the stop and wait ARQ?
once frame acknowledged transmit next frame
what is the go back n ARQ?
- send series of frames
determined by window size - if error detected discard all
frames after corrupted one - sender retransmits from
corrupted onwards
What is the selective repeat ARQ?
- only one frame transmitted
due to corrupted frame/time-
out - minimizes amount of transmission
- receivers contain storage and
logic to order frames
What is the utilisation of the ARQ protocols?
Tf/(NrTt)
What are the assumptions when analysing ARQ protocols?
acks and negative acks are error free
What is the equation for expected number of transmission of one frame (Nr)?
Nr = 1/(1-P)
What is the utilisation for stop and wait protocol?
(1-P)/(1+2a)
What is the utilisation for selective repeat protocol?
W>2a+1: U = 1-P
W<2a+1: U = [W(1-P)]/(1+2a)
What is the utilisation for go back n ARQ protocol?
W>2a+1: U = (1-P)/(1+2aP)
W<2a+1: U = [W(1-P)]/[(1+2a)
(1-P+WP)]
