高級(jí)計(jì)算機(jī)網(wǎng)絡(luò)

3.1

Data

Link

Layer

Design

Issues2Services

Provided

to

the

Network

LayerFramingError

ControlFlow

Control33.1.1

Services

provided

to

thenetwork

layerUnacknowledged

connectionless

serviceAcknowledged

connectionless

serviceAcknowledged

connection-oriented

serviceFunctions

of

the

Data

Link

Layer

(2)Relationship

between

packets

and

frames.4Services

Provided

to

Network

Layer(a)

Virtual

communication.(b)

Actual

communication.5Services

Provided

to

Network

Layer

(2)Placement

of

the

data

link

protocol.6數(shù)據(jù)鏈路層的簡(jiǎn)單模型局域網(wǎng)廣域網(wǎng)主機(jī)H1主機(jī)H2路由器R1路由器R2路由器R3網(wǎng)局域網(wǎng)

主機(jī)H1

向H2

發(fā)送數(shù)據(jù)應(yīng)用層層網(wǎng)絡(luò)層鏈路層物理層應(yīng)用層層網(wǎng)絡(luò)層鏈路層物理層網(wǎng)絡(luò)層鏈路層物理層網(wǎng)絡(luò)層鏈路層物理層網(wǎng)絡(luò)層鏈路層物理層R3從層次上來(lái)看數(shù)據(jù)的流動(dòng)R1

R2H1H27數(shù)據(jù)鏈路層的簡(jiǎn)單模型(續(xù)）主機(jī)H1主機(jī)H2路由器R1路由器R2路由器R3網(wǎng)局域網(wǎng)

局域網(wǎng) 廣域網(wǎng)僅從數(shù)據(jù)鏈路層觀察幀的流動(dòng)主機(jī)H1

向H2

發(fā)送數(shù)據(jù)鏈路層H1應(yīng)用層層網(wǎng)絡(luò)層物理層鏈路層H2應(yīng)用層層網(wǎng)絡(luò)層物理層鏈路層物理層鏈路層物理層鏈路層物理層R1網(wǎng)絡(luò)層R2網(wǎng)絡(luò)層R3網(wǎng)絡(luò)層83.1.2

Framing

Methods1. Byte

count.Flag

bytes

with

byte

stuffing.Flag

bits

with

bit

stuffing.Physical

layer

coding

violations.Framing

(3)A

frame

delimited

by

flag

bytes.Four

examples

of

byte

sequences

before

and

after

stuffing.Flag

bytes

with

byte

stuffing10Framing

(4)Flag

bytes

with

byte

stuffingStarting

and

ending

character,

with

characterstuffing

（帶字符填充的首尾界符法）Frame

flags:

DLE

STX(Start

Text),

DLE

ETX(End

Text)DLE

in

data(between

flags):

DLE-->DLE

DLE,

so

that:DLEETX-->

DLE

DLE

ETXESC=0x1B，SOH(Start

of

Header)=0x01，EOT(End

ofTransmission)=0x04Application

Example：PPP（Point-to-Point

Protocol）12Framing

(5)Application

Example：HDLCBit

stuffingThe

original

data.The

data

as

they

appear

on

the

line.The

data

as

they

are

stored

in

receiver’s

memory

after

destuffing.Flag

bits

with

bit

stuffing.Startingand

ending

flags,with

bit

stuffing（帶位填充的首尾界符法）.-（01111110）13.1.3

Error

Control（差錯(cuò)控制）ErrordetectionError

correctionRepeated

data

frameLost

frameTimer13.1.4

Flow

Control（流量控制）To

solve

the

problem

that

a

sender

wants

totransmit

frames

faster

than

the

receivercanaccept

them.Feedback-based

flow

controlRate-based

flow

control13.2

Error

Detection

and

CorrectionError-Correcting

Codes（糾錯(cuò)碼）codeword

（碼字）Hamming

distance

(10001001,10110001=>00111000,3)parity

bit糾正d比特錯(cuò)需距離為2d+1比特的編碼Error-Detecting

Codes（檢錯(cuò)碼）polynomial

code（cyclic

redundancy

code，CRC

code）檢測(cè)d比特錯(cuò)需距離為d+1比特的編碼16Error-Detecting

Codes

（3）Calculation

of

the

polynomial

codechecksum–多項(xiàng)式編碼（循環(huán)冗余碼，CRC碼）–生成多項(xiàng)式

G(x)–計(jì)算校驗(yàn)和的算法：-[see

page

197]–CRC-12

=

x12+x11+x3+x2+x1+1–CRC-16

=

x16+x15+x2+1–CRC-CCITT

=

x16+x12+x5+1–結(jié)論：具有r檢測(cè)位的多項(xiàng)式能夠檢測(cè)所有長(zhǎng)度<=r的突發(fā)錯(cuò)誤長(zhǎng)度大于r+1的錯(cuò)誤逃脫的概率為1/2r.Example

calculation

of

the

CRC173.3

Elementary

Data

Link

ProtocolsA

utopian

Simplex

Protocol（一種

的單工協(xié)議）ASimplex

Stop-and-Wait

Protocol（一種單工的停-等協(xié)議）– Error-Free

ChannelA

Simplex

Protocol

for

a

Noisy

Channel（有噪聲信道的單工協(xié)）– Noisy

Channel進(jìn)程(process)、分組(packet)和幀(frame)wait_for_event(&event),

3

events:frame_arrival:

Received

correct

framecksum_err:

Received

frame

with

checksum

errortimeout:

Timeout

when

waiting

acknowledgementElementary

Data

Link

ProtocolsImplementation

of

the

physical,

data

link,

andnetwork

layers.3.3.3

A

Simplex

Protocol

for

a

Noisy

Channel–一個(gè)肯定確認(rèn)的重傳協(xié)議(PAR)–計(jì)時(shí)器(timer)、序號(hào)(sequence)、

PAR/ARQ、時(shí)間間隔(timeout)–network

layerof

sender

hasunlimited

datatotransmit.–Discardrestrictedcondition:channel

neverdamages

or

losesframe.

Continued

→PAR:Positive

Acknowledgement

with

RetransmissionARQ:Automatic

Repeat

reQuestA

Simplex

Protocol

for

a

Noisy

Channel

(ctd.)A

positive

acknowledgement

with

retransmission

protocol.23.4

Sliding

WindowProtocols（滑動(dòng)窗口協(xié)議）Bidirectional

transmission,piggybacking（捎帶）,betteruse

of

available

bandwidthslide

windowsending

window:

a

set

of

sequence

numberscorresponding to

frameit

is

permitted

to

send

for

senderreceiving

window:

corresponding

to

the

set

of

frameswhich

is

permitted

to

accept

forreceiver23.4.2

A

Protocol

Using

Go

Back

NThe

long

round-trip

time

can

have

importantimplications

for

the

efficiency

of

the

bandwidthutilization.lite

channel

with

a

500msec

round-tripConsider

a

50kbps

sapropagation

delay.Assume

using

protocol

4

to

send

1000bit

frames

via

salite.At

t=

0

msec:

sending

the

frame.At

t=

20

msec:

the

frame

being

comple y

sent.At

t=270

msec:

the

frame

arrived

at

the

receiver.At

t=520

msec:

the

acknowledgement

arrived

back

atthesender–

The

sender

was

blocked

during

500/520

or

96

percent

of

thetime.23A

Protocol

Using

Go

Back

NPipelining

and

error

recovery.

Effect

on

an

error

whenReceiver’s

window

size

is

1.Receiver’s

window

size

is

large.Sliding

Window

Protocol

Using

Go

Back

N

(2)???接收窗口大小為W=1拋棄所有后續(xù)的幀最多允許有MAX_SEQ幀未被確認(rèn)Stop-and-wait

is

not

fitful

for

channel

which

has

long

round-trip

delay,e.g.

Sa lite

channel,270

msBidirectional

transmission,

noisy

channel,Discard

restricted

condition:

network

layer

of

sender

has

unlimiteddata

to

transmitsize

of

receiving

window

=

1,

receiver

discards

all

subsequent

framesafter

a

damaged

or

lost

data

frame.2Sliding

Window

Protocol

Using

Go

Back

N

(9)Simulation

of

multiple

timers

in

software.23.4.3

A

Sliding

Window

Protocol

UsingSelective

Repeat–

允許接收后續(xù)的幀（接收窗口>1）窗口大小為W<=(MAX_SEQ+1)/2所需緩沖器的數(shù)量=W所需計(jì)時(shí)器的數(shù)量=W否定性確認(rèn)幀-NAK2A

Sliding

Window

Protocol

Using

Selective

Repeat

(6)Initial

situation

with

a

window

size

7.After

7

frames

sent

and

received,

but

not

acknowledged.Initial

situation

with

a

window

size

of

4.After

4

frames

sent

and

received,but

not

acknowledged.23.5

Example

Data

Link

ProtocolsHDLC

–

High-Level

Data

Link

ControlThe

Data

Link

Layer

in

the

Internet

（PPP）23.5.1

High-Level

Data

Link

ControlSDLC(IBM’SNA)→AD

(ANSI)

→HDLC(ISO)→LAP(CCITT)→LAPB(X.25)bit-oriented

protocolframe

format-[see

fig

3-24]flag

sequence(01111110)、the

minimum

frame：three

fields、32bitsthree

kinds

of

frames：Information、Supervisory、Unnumbered-[see

fig3-25]Content

in

4th

edition：2Content

in

4th

edition：High-Level

Data

Link

Control

(2)3Seq

---

sender

seq(like

former

protocol

5

)Next

---

expected

frame

seq,

different

from

former

ack,it

is

(ack+1)

mod

8Information

frame(信息幀):Supervisory

frame(

幀):RR(Receive

Ready),接收準(zhǔn)備就緒RNR(Receive

Not

Ready):

to

implement

flow

controlREJ(Reject):likeNAK

frame,從Next起的所有幀都被否認(rèn),但確認(rèn)序號(hào)為Next及其以前的各幀SREJ(Selective

Reject),選擇性Unnumbered

frame(無(wú)序號(hào)幀):request

to

establish

connection:

SNRM(Set

Normal

Response

Mode),SABM(set

asynchronous

balanced

mode)request

to

disconnect:

DISC(Disconnect)response

frame:

UA(unnumbered

acknowledgement)report

severe

error:

FRMR(FRaMe

Reject)Content

in

4th

edition：High-Level

Data

Link

Control

(3)33.5.2

The

Data

Link

Layer

in

the

InternetA

homeal

computer

acting

as

an

internethost.Content

in

4th

edition：3Content

in

4th

edition：用戶撥號(hào)入網(wǎng)的示意圖路由器調(diào)制解調(diào)器調(diào)制解調(diào)器因特網(wǎng)服務(wù)提供者(ISP)用戶家庭撥號(hào)

線使用TCP/IP

的PPP

連接使用TCP/IP

的客戶進(jìn)程路由選擇進(jìn)程至因特網(wǎng)…PC

機(jī)3PPP

協(xié)議1992

年制訂了PPP

協(xié)議。經(jīng)過(guò)1993

年和1994年的修訂，現(xiàn)在的PPP

協(xié)議已成為因特網(wǎng)的正式標(biāo)準(zhǔn)[RFC

1661]。PPP協(xié)議有三個(gè)組成部分一個(gè)將IP

數(shù)據(jù)報(bào)封裝到串行鏈路的方法。鏈路控制協(xié)議LCP

(Link

Control

Protocol)。網(wǎng)絡(luò)控制協(xié)議NCP(Network

Control

Protocol)。3Content

in

4th

edition：Content

in

4th

edition：PPP

協(xié)議的幀格式PPP

的幀格式和HDLC

的相似。標(biāo)志字段F

仍為0x7E（符號(hào)“0x”表示后面的字符是用十六進(jìn)制表示。十六進(jìn)制的7E

的二進(jìn)制表示是01111110）。地址字段A

只置為0xFF。地址字段實(shí)際上并不起作用?？刂谱侄蜟

通常置為0x03。PPP

是面向字節(jié)的，所有的PPP

幀的長(zhǎng)度都是整數(shù)字節(jié)。3Content

in

4th

edition：PPP

協(xié)議的幀格式IP

數(shù)據(jù)報(bào)字節(jié)

1

1

1

2PPP

幀PPP

有一個(gè)2

個(gè)字節(jié)的協(xié)議字段。當(dāng)協(xié)議字段為0x0021

時(shí)，PPP

幀的信息字段就是IP

數(shù)據(jù)報(bào)。若為0xC021,則信息字段是PPP

鏈路控制數(shù)據(jù)。若為0x8021，則表示這是網(wǎng)絡(luò)控制數(shù)據(jù)。先發(fā)送F7EAFFC03FCSF7E協(xié)議信

息