計(jì)算機(jī)網(wǎng)絡(luò)講義

Chapter4：NetworkLayer

Chaptergoals：Overview：

口understandprinciples口networklayerservices

behindnetworklayer□routingprinciple：path

services：selection

orouting(pathselection)口hierarchicalrouting

odealingwithscale□IP

ohowarouterworks

口Internetroutingprotocols

□advancedtopics：IPv6,

reliabletransfer

multicast

ointra-domain

口instantiationand

Qinter-domain

implementationinthe

Internet口what'sinsidearouter?

口IPv6

口multicast

4：NetworkLayer4a-1

Networklayerfunctions

口transportpacketfromapplication

transport

sendingtoreceivinghostsnetwork

network

physical

口networklayerprotocolsinnetworkdatalinknetwork

datalinkphysicaldatalink

every\\QSX,routerphysicalphysical

network

threeimportantfunctions：???datalink

physicalnetwork

datalink

□pathdetermination：routephysical

takenbypacketsfromsourcenetwork

network

datalink7

todest.Routingalgorithmsdatalinkphysical

physical

□switching：movepacketsfromnetwork

datalinkJication

routersinputtoappropriatephysicaltransport

network

routeroutput

physical

□ca//setup：somenetwork

architecturesrequirerouter

callsetupalongpathbefore

dataflows

4：NetworkLayer4a-2

Networkservicemodel

Q：Whatservicemodel

for"channel”Themostimportant

transportingpacketsabstractionprovided

fromsendertobynetworklayer：

receiver?

u

-o□guaranteedbandwidth?virtualcircuit

+-口preservationofinter-packet

Door

上timing(nojitter)?

Sdatagram?

q

D□loss-freedelivery?

2

□in-orderdelivery?

<>J

N」□congestionfeedbackto

Ssender?

4：NetworkLayer4a-3

Virtualcircuits

"source-to-destpathbehavesmuchliketelephone

circuit11

□performance-wise

□networkactionsalongsource-to-destpath

□callsetup,teardownforeachcallbeforedatacanflow

□eachpacketcarriesVCidentifier(notdestinationhostlb)

□everyrouteronsource-destpathsmaintain“state"for

eachpassingconnection

otransport-layerconnectiononlyinvolvedtwoendsystems

□link,routerresources(bandwidth,buffers)maybe

allocatedVC

otogetcircuit-likeperf.

4：NetworkLayer4a-4

Virtualcircuits：signalingprotocols

□usedtosetup,maintainteardownVC

□usedinATM,frame-relay,X.25

□notusedintodaysInternet

齷

application

6.Receivedataapplication

transport5Dataflowbegins

Callconnected3.Accept

datalinkInitiatecall聲不2.incomingc|

Physical■l=====y[^hysical_1

4：NetworkLayer4a-5

Datagramnetworks￡theInternetmodel

□nocallsetupatnetworklayer

□routers：nostateaboutend-to-endconnections

□nonetwork-levelconceptof''connection"

□packetstypicallyroutedusingdestinationhostlb

□packetsbetweensamesource-destpairmaytake

differentpaths

application

transport

network

datalink

physical

4：NetworkLayer4a-6

Networklayerservicemodels：

Guarantees?

NetworkServiceCongestion

ArchitectureModelBandwidthLossOrderTimingfeedback

Internetbesteffortnonenononono(inferred

vialoss)

ATMCBRconstantyesyesyesno

ratecongestion

ATMVBRguaranteedyesyesyesno

ratecongestion

ATMABRguaranteednoyesnoyes

minimum

ATMUBRnonenoyesnono

□Internetmodelbeingextented：Intserv,Diffserv

oChapter6

4：NetworkLayer4a-7

DatagramorVCnetwork：why?

InternetATM

□dataexchangeamongnevolvedfromtelephony

computers

□humanconversation：

o"elastic"service,nostrict

ostricttiming,reliability

timingreq.

requirements

□"smart"endsystems

oneedforguaranteed

(computers)

service

ocanadapt,perform

□"dumb"endsystems

control,errorrecovery

otelephones

osimpleinsidenetwork,

complexityat''edge"ocomplexityinside

network

□manylinktypes

odifferentcharacteristics

ouniformservicedifficult

4：NetworkLayer4a-8

Routing

-Routingprotocol----------

Goal：determine"good"path

(sequenceofrouters)thru

networkfromsourcetodest.

Graphabstractionfor

routingalgorithms：

□graphnodesare

routers□“good"path：

□graphedgesareotypicallymeansminimum

physicallinkscostpath

Qlinkcost：delay,$cost,ootherdef'spossible

orcongestionlevel

4：NetworkLayer4a-9

RoutingAlgorithmclassification

GlobalordecentralizedStaticordynamic?

information?Static：

Global：□routeschangeslowlyover

□allroutershavecompletetime

topology,linkcostinfoDynamic：

□''linkstate"algorithms□routeschangemorequickly

Decentralized：operiodicupdate

□routerknowsphysically-Qinresponsetolinkcost

connectedneighbors,linkchanges

coststoneighbors

□iterativeprocessof

computation,exchangeof

infowithneighbors

□''distancevector"algorithms

4：NetworkLayer4a-10

ALink-StateRoutingAlgorithm

Dijkstra'salgorithmNotation：

口nettopology,linkcosts□C(i,j)：linkcostfromnodei

knowntooilnodestoj.costinfiniteifnot

oaccomplishedvia''linkdirectneighbors

statebroadcast"

口D(v)：currentvalueofcost

ooilnodeshavesameinfoofpathfromsourceto

口computesleastcostpathsdest.V

fromonenode('source")to

□p(v)：predecessornode

allothernodes

alongpathfromsourceto

Qgivesroutingtableforv,thatisnextv

thatnode

□N：setofnodeswhose

□iterative：afterk

leastcostpathdefinitively

iterations,knowleastcost

known

pathtokdest.'s

4：NetworkLayer4a-11

DijsktrdsAlgorithm

1Initialization:

2N={A}

3forallnodesv

4ifvadjacenttoA

5thenD(v)=c(A,v)

6elseD(v)=infty

7

Loop

9findwnotinNsuchthatD(w)isaminimum

10addwtoN

11updateD(v)forallvadjacenttowandnotinN:

12D(v)=min(D(v),D(w)+c(w,v))

13/*newcosttoviseitheroldcosttovorknown

14shortestpathcosttowpluscostfromwtov*/

\15untilallnodesinN

4：NetworkLayer4a-12

Dijkstra'salgorithm：example

StepstartND(B),p(B)D(C),p(C)D(D),p(D)D(E),p(E)D(F),p(F)

―?OA2,A5.A1,Ainfinityinfinity

----AD2,A4,D2,Dinfinity

-?2ADE2,A3.E4,E

?3ADEB3.E4,E

----?4ADEBC4.E

5ADEBCF

1

4：NetworkLayer4a-13

Dijkstra'salgorithm,discussion

Algorithmcomplexity：nnodes

□eachiteration：needtocheckoilnodes,wznotinN

口n*(n+l)/2comparisons：O(n**2)

□moreefficientimplementationspossible：O(nlogn)

Oscillationspossible：

□e.g.zlinkcost=amountofcarriedtraffic

...recompute...recompute...recompute

in汁ially

routing

4：NetworkLayer4a-14

DistanceVectorRoutingAlgorithm

iterative：

DistanceTabledatastructure

□continuesuntilno

nodesexchangeinfo.□eachnodehasitsown

口self-terminatingno口rowforeachpossibledestination

"signal"tostop□columnforeachdirectly-

attachedneighbortonode

asynchronous：

□example：innodeXfordest.Y

□nodesneednotz

vianeighborZ：

exchangeinfo/iterate

inlockstep!

distributed：distancefromXto

X一Y,viaZasnexthop

口eachnodeD(Y,Z)

communicateswith=c(X,Z)+min{Dz(Y,w)}

directly-attachedw

neighbors

4：NetworkLayer4a-15

DistanceTable：example

costtodestinationvia

DE()ABD

Adi4

?

oUB78

J-

Ene

D(C,D)=c(E,D)+min{DD(C,w)}u

j-c69⑷

ws①

=2+2=4p1

E②

n

D(A,D)=c(E,D)+min{DD(A,w)}D41

w

=2+3=5

Eloop!

D(A,B)=c(E,B)+min{D*A,w)}

w

=8+6=14

loop!

4：NetworkLayer4a-16

Distancetablegivesroutingtable

costtodestinationvia

DE()ABDOutgoinglink

0touse,cost

A.14AA1

5

uB78uBD

oo

l一-

El

Ue

-u

l一

sc69wcD4

①①

pp

D41DD4

DistancetableRoutingtable

4：NetworkLayer4a-17

DistanceVectorRouting：overview

Iterative,asynchronous：Eachnode：

eachlocaliterationcaused

by：

□locallinkcostchangewaitfor(changeinlocallink

口messagefromneighbor：itscostofmsgfromneighbor)

leastcostpathchange

fromneighbor、r

Distributed：recomputedistancetable

口eachnodenotifies

neighborsonlywhenits■

ifleastcostpathtoanydest

leastcostpathtoany

destinationchangeshaschanged,notify

oneighborsthennotifyneighbors

theirneighborsif

necessary

4：NetworkLayer4a-18

DistanceVectorAlgorithm：

Atoilnodes,X：

1Initialization:

2foralladjacentnodesv:

3DX(*,v)=infty/*the*operatormeans"forallrows"*/

4D8v,v)=c(X,v)

5foralldestinations,y

6sendminD"y,w)toeachneighbor/*woverallX'sneighbors*/

w'

4：NetworkLayer4a-19

DistanceVectorAlgorithm(cont.)：

18loop

9wait(untilIseealinkcostchangetoneighborV

10oruntilIreceiveupdatefromneighborV)

11

12if(c(X,V)changesbyd)

13/*changecosttoalldest'svianeighborvbyd*/

14/*note:dcouldbepositiveornegative*/

15foralldestinationsy:DX(y,V)=DX(y,V)+d

16

17elseif(updatereceivedfromVwrtdestinationY)

18/*shortestpathfromVtosomeYhaschanged*/

19/*VhassentanewvalueforitsminDV(Y,w)*/

20/*callthisreceivednewvalueis"newval"*/

21forthesingledestinationy:DX(Y,V)=c(X,V)+newval

22

23ifwehaveanewminDx(Y,w)foranydestinationY

24sendnewvalueofminDpY,w)toallneighbors

25w

26forever4：NetworkLayer4a-20

_I

DistanceVectorAlgorithm：example

4：NetworkLayer4a-21

DistanceVectorAlgorithm：example

Ycostvia

埒YZ

丫②8

Z③7

Y7

A

D(Y,Z)=C(X,Z)+minw{D(Y,w)}

=7+1=8

YY

D,乙Y)=c(X,Y)+minw{D(乙w)}

=2+1=3

4：NetworkLayer4a-22

DistanceVector：linkcostchanges

Linkcostchanges：

□nodedetectslocallinkcostchange

口updatesdistancetable(line15)

□ifcostchangeinleastcostpath,

notifyneighbors(lines23,24)

algorithm

“goodterminates

news

travels

fast"

c(X,Y)

change

time

o1

4：NetworkLayer4a-23

DistanceVector：linkcostchanges

Linkcostchanges：

口goodnewstravelsfast

□badnewstravelsslow-

''counttoinfinity"problem!

4：NetworkLayer4a-24

Problem:RoutingLoops

Network1,Unreachable

AlternateRoute:UseA

Network1,Distance4

?Alternateroutes,slowconvergence,inconsistentrouting

4：NetworkLayer4a-25

Problem:CountingtoInfinity

Network1,Distance6Network1,DistanceTJ

Network1Down

]Network1,Di&tance4

?Routingloopsincrementthedistancevector

4：NetworkLayer4a-26

Solution：poisonedreverse

IfZroutesthroughYtogettoX:

□ZtellsYits(Z's)distancetoXis

infinite(soYwon'troutetoXviaZ)

□willthiscompletelysolvecountto50

infinityproblem?

4：NetworkLayer4a-27

Solution:DefiningaMaximum

Network1.Distance14

Networlc1,Distance13

[Network1,Distance12

Networx1,Distance15

Network1Down

RoutingTable

MaximumMetricIs16

Network1isUnreachable

?Specifyamaximumdistancevectormetricasinfinity

4：NetworkLayer4a-28

Solution:SplitHorizon

B:Donotupdate

?routerAabout

Iroutestonetwork1

|Network

總

Network1Down

D:Donotupdate

routerAabout

routestonetwork1

?Ifyoulearnaprotocol'srouteonaninterface,donotsend

informationaboutthatroutebackoutthatinterface

4：NetworkLayer4a-29

Solution:Hold-DownTimers

Updateafter

UpdateafterI\Hold-DownTime

LHold.DownTime]

Network1Down

Updateafter

UpdateafterHold-DownTime

Hold-DownTime

.Network1down,

thenbackupforatime,

thenbackdownonceagain

?Routersignorenetworkupdateinformationforsomeperiod

4：NetworkLayer4a-30

ComparisonofLSandDValgorithms

MessagecomplexityRobustness：whathappens

口LSwithnnodes,Elinks,ifroutermalfunctions?

O(nE)msgssenteachL5：

□bV：exchangebetween

onodecanadvertise

neighborsonly

incorrectlinkcost

□convergencetimevaries

oeachnodecomputesonly

SpeedofConvergenceitsowntable

□LSiO(n**2)algorithmDV：

requiresO(nE)msgsoDVnodecanadvertise

omayhaveoscillationsincorrectpathcost

□DV：convergencetimevariesoeachnode'stableusedby

omayberoutingloopsothers

?errorpropagatethru

ocount-to-infinityproblem

network

4：NetworkLayer4a-31

HierarchicalRouting

Ourroutingstudythusfar-idealization

□oilroutersidentical

□network"flat"

...nottrueinpractice

scale：with50millionadministrativeautonomy

destinations：口internet二networkof

口can'tstorealldust'sinnetworks

routingtables!□eachnetworkadminmay

□routingtableexchangewanttocontrolroutinginits

wouldswamplinks!ownnetwork

4：NetworkLayer4a-32

HierarchicalRouting

□aggregateroutersintor-gatewayrouters------

regions,'autonomous□specialroutersinAS

systems"(AS)□runintra-ASrouting

□routersinsameASrunprotocolwithallother

routersinAS

sameroutingprotocol

□alsoresponsiblefor

o“intra-AS"routing

routingtodestinations

protocol

outsideAS

oroutersindifferentAS

oruninter-ASrouting

canrundifferentintra-

protocolwithother

ASroutingprotocol

gatewayrouters

4：NetworkLayer4a-33

工ntra-ASand工nter-ASrouting

Gateways：

,performinter-AS

A.aroutingamongst

themselves

aB,performintra-AS

routerswithother

routersintheir

Ab

AS

networklayer

inter-AS,intra-ASlinklayer

routingin

physicallayer

gatewayA.c

to/fromrom

A.b

to/fromA.d

4：NetworkLayer4a-34

工ntra-ASand工nter-ASrouting

Inter-AS

C.brouting

betweenB

A.aAandBHost

A.h2

aB

Host

Intra-ASrouting

hl

Aw汁h(huán)inASB

Intra-ASrouting

withinASA

□Wellexaminespecificinter-ASandintra-AS

Internetroutingprotocolsshortly

4：NetworkLayer4a-35

TheInternetNetworklayer

Host,routernetworklayerfunctions：

Transportlayer：TCP,UbP

RoutingprotocolsIPprotocol

,pathselection,addressingconventions

?RIP,O5PF,BGP,dataoramformat

Network,packethandlingconventions

layerrouting

tabeICMPDrotocol

,errorreporting

?router"signaling”

Linklayer

physicallayer

4：NetworkLayer4a-36

IPAddressing：introduction

□IPaddress：32-bit

identifierforhost,

routerinterface

□interface：connection

betweenhost,router

andphysicallink

orouterstypicallyhave

multipleinterfaces[1

ohostmayhavemultiple

interfaces

QIPaddresses

=11011111000000010000000100000001

associatedwithI________IIIII]

interface,nothost,

223111

router

4：NetworkLayer4a-37

IPAddressing

Octet(8bits).Octet(8bits).Octet(8bits).Octet(8bits)

11000000000001010010001000001011

EQUALS

19253411

4：NetworkLayer4a-38

IPAddressing

□IPaddress：K

onetworkpart(high

orderbits)

ohostpart(loworder

bits)

□What'sanetwork?

(fromIPaddress

perspective)

odeviceinterfaceswith

samenetworkpartof

IPaddress

networkconsistingof3IPnetworks

ocanphysicallyreach(forIPaddressesstartingwith223,

eachotherwithoutfirst24bitsarenetworkaddress)

interveningrouter

4：NetworkLayer4a-39

IPAddressing

Howtofindthe

networks?

□Detacheach

interfacefrom

router,host

□create''islandsof

isolatednetworks

Interconnected

systemconsisting

ofsixnetworks

4：NetworkLayer4a-40

IPAddresses

givennotionof"network",let'sre-examineIPaddresses：

“class-full“addressing：

4：NetworkLayer4a-41

IPAddressing

1Byte1Byte1Byte1Byte

—8Bits-，8Bits—8Bits-*8Bits

.122.204

4：NetworkLayer4a-42

IPAddressing

------------------------------A32Bits<------------------------------

1Byte1Byte1Byte1Byte

?8Bits—

0

4：NetworkLayer4a-43

SubnetsandSubnetMasks

□Allowarbitrarycomplexityofinternetworked

LANswithinorganization

口Insulateoverallinternetfromgrowthof

networknumbersandroutingcomplexity

□Sitelookstorestofinternetlikesingle

network