Network architecture

(1)

Telecommunication Protocols Laboratory Course

Lecture 2

(2)

March 11, 2004 http://www.abo.fi/~lpetre/teleprot/teleprot.html 2

Last time

• We examined some key terms: protocol, service, layer, network architecture

• We examined some reference models for network architecture – OSI/ISO and TCP/IP

• We delimited a certain network architecture to be followed

(3)

Network architecture

(4)

Service and Protocols

(5)

Assignments

• Each network layer has specific protocols

• Each team will choose one protocol from each layer and offer a simulation for it

• The simulation has to emphasize the protocol features corresponding to its layer – it does not need to be

complicated

• Each assignment is documented and logged

• The programs are sent to vpreotea@abo.fi (the course assistant – Viorel Preoteasa)

(6)

Timetable

• We will cover five (sub)layers: DLL, MAC, NL, TL, AL

• First assignment: 25.3 – DLL protocol

• 18.3 – groups formed, log and documentation started, DLL protocol chosen

• Lectures: 18.3, 25.3, 1.4, 8.4

• Remaining time: feedback on request, solving assignments time

• Grading each protocol will be detailed later, same with final grade

• Today we study data link layer (DLL) protocols

(7)

The Data Link Layer

• Studies algorithms for achieving reliable and efficient communication between 2 adjacent machines at DLL

• Adjacent machines: connected by a wire-like communication channel

o Bits delivered in exactly the same order in which they are sent

• Problems to be handled

o Errors made by communication circuits

o Finite data rate of communication circuits

o Non-zero propagation delay

(8)

Functions of the Data Link Layer

• Provide service interface to the network layer

• Dealing with transmission errors

• Regulating data flow

• Slow receivers not swamped by fast senders

(9)

Functions of the Data Link Layer (2)

Relationship between packets and frames.

(10)

Data Link Layer Design Issues

• Services Provided to the Network Layer

• Framing

• Error Control

• Flow Control

(11)

Services Provided to Network Layer

(a) Virtual communication. (b) Actual communication.

(12)

DLL services

• Unacknowledged connectionless service

• Acknowledged connectionless service

• Acknowledged connection-oriented service

(13)

Framing idea

• To provide service to NL, DLL uses service of PL

• PL accepts a bit stream and delivers it to destination

• Bit stream not guaranteed to be error-free

o It is up to DLL to detect and, if necessary, to correct errors

• DLL breaks the bit stream into discrete frames and computes some checksum C for each frame

• At destination the checksum of the received frames recomputed in C’

• If C≠C’ DLL knows an error occurred

• Framing = breaking the bit stream into frames

(14)

Framing methods

• Character count

• Flag bytes with byte stuffing

• Starting and ending flags with bit stuffing

• PL coding violations

(15)

Framing

A character stream. (a) Without errors. (b) With one error.

(16)

Framing (2)

(a) A frame delimited by flag bytes.

(b) Four examples of byte sequences before and after stuffing.

(17)

Framing (3)

Bit stuffing

(a) The original data.

(b) The data as they appear on the line.

(18)

Error control

• DLL has to ensure that all frames are delivered to NL at destination in right order and only once

• Tools

o Acknowledgements

o Timers

o Sequence numbers

(19)

Flow control

• Occurs in DLL and at higher layers

• What to do with fast senders that eventually swamp slow receivers

• 2 methods

o Feedback-based flow control

o Rate-based flow control (never used at DLL)

(20)

Error Detection and Correction

• Errors are common on twisted copper pairs and in wireless communication

• On reliable channels

o Error-Detecting Codes

• On prone-to-error channels

o Error-Correcting Codes

(21)

Elementary Data Link Protocols

1. An Unrestricted Simplex Protocol 2. A Simplex Stop-and-Wait Protocol

3. A Simplex Protocol for a Noisy Channel

• Reliable, connection-oriented service

• One direction, later both

• Infinite supply of data from NL, later not

(22)

Protocol Definitions

Continued Æ Some definitions needed in the protocols to follow.

(23)

Protocol

Definitions (ctd.)

Some definitions needed in the

protocols to follow.

(24)

Unrestricted simplex protocol

• Data transmitted in one direction only

• Both transmitting and receiving layers always ready

• Processing time ignored

• Infinite buffer space available

• Communication channel never loses/damages frames

(25)

Unrestricted Simplex

Protocol

(26)

A simplex stop-and-wait protocol

• Infinite buffer not any longer

• Solution: receiver sends acknowledgement frame (just a

“dummy” frame) to sender, which gives the latter permission to transmit the next frame

• Exp of flow control

(27)

Simplex Stop-and-

Wait

Protocol

(28)

A simplex protocol for a noisy channel

• Errors are now possible

• Solution: timers and sequence numbers

(29)

A Simplex Protocol for a Noisy Channel

A positive

acknowledgement with retransmission

protocol.

(30)

A Simplex Protocol for a Noisy Channel (ctd.)

A positive acknowledgement with retransmission protocol.

(31)

Sliding Window Protocols

• Need to transmit data in both directions

o For this, piggybacking used

• Idea

o Sender maintains a a set of sequence numbers, for frames it is permitted to send => sending window

o Receiver maintains a receiving window, for frames it is permitted to accept => receiving window

o Buffers needed

o Receiver window keeps its size

(32)

Sliding Window Protocols (2)

A sliding window of size 1.

(a) Initially.

(b) After the first frame has been sent.

(c) After the first frame has been received.

(d) After the first acknowledgement has been received.

(33)

A One-Bit Sliding Window

Protocol

(34)

A One-Bit Sliding Window Protocol

(ctd.)

(35)

A One-Bit Sliding Window Protocol (2)

Two scenarios for protocol 4. (a) Normal case. (b) Abnormal case. The notation is (seq, ack, packet number). An asterisk indicates where a network layer accepts a packet.

(36)

Other protocols

• Assumption: processing time not ignored

o With sender waiting ack before transmitting next frame, bad efficiency is achieved

• Solution: the sender transmits up to w frames before blocking for ack => sliding window of length w

• With an unreliable channel, 2 solutions

o Go back N

o Selective repeat

(37)

Go Back N and Selective Repeat

(38)

Protocol Verification

• Finite State Machined Models

• Petri Net Models

(39)

Finite State Machined Models

(40)

Petri Net Models

A Petri net with two places and two transitions.

(41)

Petri Net Models (2)

(42)

Example Data Link Protocols

• HDLC – High-Level Data Link Control

o Bit stuffing for framing

o Sliding window for flow control

o Acknowledgements also for control frames

• PPP – Point-to-point protocol

o Multi-protocol framing mechanism

o Byte stuffing for framing

o Sliding window for flow control

o Handles errors detection

o Allows IP addresses to be negotiated at connection time

o Permits authentication

(43)

The Data Link Layer in the Internet

A home personal computer acting as an internet host.