Data Layer
Note on 17 Jul 2002
Framing methods
Character count
Data Layer
Responsibility of the data layer- Framing
- Error detection (sometimes)
- Error Correction (sometimes)
- Flow Control
- Broadcast channels (MAS sub-layer)
- Unacknowledged connectionless service
- Acknowledged connectionless service
- Acknowledged connnection-oriented service
- Used to help data link layer detect and correct errors
- Data stream is aplit up into regular chunks (frames)
- Also need to consider timing issues
- Synchronous - common clock or encoded timing information
- Asynchronous - no common clock
- Primarily used on slow serial links (75-115200b/s)
- No common clock
- Individual characters are enclosed by known start and stop bits
- Signal is then split up into chunks and centre point of chunks is analysed
- Faster devices (9600+b/s)
- Can use common network clock (known as heartbeat or clock encoding
- Sets (frames) of characters are enclosed by known start/stop characters
- no matter how much the width of the bit data link layer still consider as 1 (regardless how long is last for)
- Character count
- Starting & stopping characters with character stuffing
- Starting and stopping bits with bit stuffing
- Physical layer coding violations
- Simplest method, but rarely used by itself
- Each frame is prefixed with the number of characters contained in the frames
- Problems occur when frame is corrupted
- how do we know when new frame starts?
- how do we know where the checksum is to detect errors?
- Common method - solves synchronisation problem with character count
- Frame starts with characters DLE, STX and ends with DLE, ETX
- What happens when we get DLE, ETX/STX in text?
- Solution is to prefix all DLE's in text with an additional DLE
- Similar to starting and stopping characters, but users bit patterns rather than ASCII code
- Each frame starts and stops with special flag (e.g. 01111110)
- On transmission, data link layer tries to ensure that flag does not occur in the data - this is done bu adding a suitable extra bit (e.g. if data link layer detects 11111 in a row in the frame, it will add extra 0)
- On receiving, data link layer removes added bits (if data link layer detects 111110 following a row in the frame, it will delete the extra 0)
- Can only be used where encoding on physical layer has some form of redundancy (e.g. ME)
- Invalid codes are used to signal start/end of transimission
- Sometimes known (incorrectly) as Out of Bandwidth Transmission
- Unless we do not care about the frame getting through correctly we have to provide means to detect or correct errors
- Sometimes it is enough to detect errors and ask for retransmission - other times it is advantagous to try and correct errors
- Also need to consider types of error
- Single bit
- Burst errors
- n=m+r (where m=length of data, r = number of checkbits, n=total length of message)
- Hamming Distance = m1XOR m2
- If we presume that there are 2m possible legal messages and we can compute the HD for each possible pair of legal messages we can find the pair with the smallest HD - this is said to be the HD of the code
- Therefore to detect d errors we need a d+l HD code and to correct erros we need a 2d+l HD code
- Creating a Hamming code
- In a given codeword
- Let the powers of 2 contain parity bits
- Let the other digits contain message patterns
- In a given codeword
- Using a Hamming Code
- Where a codeword is received
- Set counter k to zero
- Examine each check bit in turn to see if it has the correct parity
- If checkbit does not have the correct parity add it to k
- After checking codeword, if k=0 then codeword is OK, if k>0 then k = position of error
- Create matrix of k conssecutive codewords, one codeword per row
- Transmit matrix, column at a time, from left to right
- Receiver reassembles matrix and reads codewords off rows
- This gives a Hamming code immunity from a burst of length k or less
- CRC is based on Module2 devision
- Bit strings are represented as polynomials with coefficients 1 & 0
- Both sender & receiver agree of polynomial generator G(x) which will be used to generate a checksum
- The sender appends a bit pattern to the end of the message so that the message is divisible by G(x)
- The receiver divides the message by G(x) - if remainder is zero then there has been no errors, if it is not then an error has occurred
- r=degree of G(x)
- m=message
- M=m with r'0's appended
- Rem = remainder of M (modulo 2 division) G(x)
- Transmit=M (modulo 2 subtraction) Rem
- If we have x+1 as a team in G(x) then we will catch all errors that invert an odd number of bits
- A polynomial with r check bits will detect
- all errors of length <=r
- with probability of 0.5 <sup>r-1</sup> errors of length <i>r+1</i>
- with probability of 0.5 <sup>r</sup> errors of length > = r +1
- Requirement for Data Link Layer Protocol
- Definite interface between Data & Network layer
- Definite interface between Data & Physical layer
- Data layers communicate via frames
- There exists some form of timer
- conet
MAX_PKT = 1024; MAX_SEQ = 65535
type
Tseq_nr = integer;
TEvant = (frame-arrival,ckeum_err, timeout);
Tpacket = array (1..MAX_PKT) of char;
Tframe_kind = (data, ack, nak);
Tframe = record
kind : Tframe_kind
segNo, ackNo, Tseq_nr;
info : Tpacket;
end;
procedure wait_for_event (var event:Tevent);
procedure from_network_layer(var apacket:TPacket);
procedure to_network_layer (apacket; TPacket);
procedure from_physical_layer(var aframe; Tframe);
procedure to_physical_layer(aframe; Tframe);
procedure start_timer (k:TSeq_nr);
procedure stop_timer (k:TSeq_nr);
procedure start_ack_timer(k:TSeq_nr);
procedure stop_ack_timer(k:TSeq_nr);
procedure enable_network_layer;
procedure disable_network_layer;
procedure inc_seq;
- procedure sender;
var f:Tframe;
buf:TPacket;
Begin
while (true; do begin
from_network_layer(buf);
f.info:ebuf;
to_pyhsical_layer(f);
end;
procedure receiver;
var f:Tframe;
buf:Tevent
begin
while (true)
do begin
wait_for_event(s):
from_physical_layer(f);
to_network_layer(f.info);
end;
end;
- procedure sender;
var
f:Tframe;
buf: TPacket;
ev:Tevent;
begin
while (true)
do begin
from_network_layer (buf);
f.info := buf;
to_physical_layer(f);
wait_for_event(ev);
end;
end;
procedure receiver;
var fn, fr: Tframe;
e:Tevent;
begin
while (true)
do begin
wait_for_event(e);
from_physical_layer(fr);
to_network_layer(fr.info);
to_physical_layer(fn);
end
end
-
procedure sender;
var next_frame_to_send:Treq_nr;
f:Tframe;
buf:TPacket;
ev:Tevent;
begin
next_frame_to_send:=0
from_network_layer(buf);
while (true)
do begin
f.info:=buf;
f.SegNo:=next_frame_to_send;
to_physical_layer(f);
start_timer(f.SegNo);
wait_for_event(ev);
if (ev = frame_arrival) then
begin
from_physical_layer(s);
if (s.ack= next_frame_to_send) then
begin
from_physical_layer(e);
if (s.ack=next_frame_to_send) then
begin
from_physical_layer(buf)
inc(next_frame_to_send)
end
end
end
end
- procedure receiver;
var frame_expected:TSeq_no;
fs, fr: Tframe;
e:Tevent;
begin
frame_expected:=0;
while (true)
do begin
wait_for_event(e);
if (e- frame_arrival) then
begin
from_physical_layer(fr);
if (fr= frame_expected) then
begin
to_network_layer(fr.info);
inc(frame_expected);
end;
fs.ack := frame_expected-1;
to_physical_layer(fs);
end;
end
end
- Last 3 protocols
- waste bandwidth (they are simplex)
- have problems with early timeouts
- have problems with ordering
- A better solution is to use
- Piggybacking
- A sliding window
- In a SWP we allow the sender and receiver to send and receive frames out of order.
- However we still must
- ensure that the receiver does not get swamped
- ensure that the packets must be passed to the network layer in the correct order
- The Sender maintains
- a series of n buffers
- a circular sequence (window) of frames it can send with maximum value n-1
- the bottom (b) and top (t) numbers in the sequence
- When the data layer receives a packet from the network layer, it increments t stores the packet in buffer b, b is incremented and the buffer b is emptied
- If all the buffers are full, then the network layer must be switched off
- The receiver maintains
- a series of n buffers
- a circular sequence (window) of frames it can receive with maximum value n-1
- the bottom (b) and top (t) numbers in the sequences
- Any frame received that falls outside the window is automatically discarded.
- If a frame is received that falls within the window an acknowledgment is generated
- Any frame received that correcponds to b then that frame is passed to the network layer and b and t are incremented
- Go back n
- If error occurs receiver sends no acknowledgments for error frame or any subsequent frame
- Eventually sender will time out and send erroneous frame and all other frames again
- Selective repeat
- Acknowledge all good frames that fit within window
- Sender will eventually timeout erroneous frames and resend
- Not present as such
- LAN's use MAC protocols (ethernet or Token Ring)
- Dial-up connections use
- SLIP/cSLIP
- PPP
- Serial Line IP (RFC 1055)
- Raw IP packets are sent with framing flag (0xC0)
- cSLIP variant does header compression
- Simple, easy to implement, but many problems
- No error detection/correction
- Supports only IP
- SLIP versions maybe incompatible, not internet standard many different version exist
- Point-to-Point Protocol (RFCs 1661, 1662, 1663)
- PPP supports
- a good framing method & error detection
- a link protocol for creating, testing, negotiating options & destroying lines
- a way to negotiate network layer options independent of the network layer protocol used
- multiple protocols (not just IP)
- Dynamic allocation of IP addresses
- authentication
Comments
Post a Comment