计算机科学与技术学硕-现代计算机网络讲义-现代计算机网络讲义5

Chapter5

TheNetworkLayer

Goal:end-to-endtransmission

14:32

,5.1NetworkLayerDesignIsues

■Store-and-ForwardPacketSwitching

■ServicesProvidedtotheTransportLayer

■ImplementationofConnectionlessService

■ImplementationofConnection-Oriented

Service

■ComparisonofVirtual-CircuitandDatagram

Subnets

14:322

5.1.1Store-and-ForwardPacketSwitching

■Theenvironmentofthenetworklayer

protocols.

■Storeandforward

■Route

RouterCarrier'sequipment

\/

ProcessP1Packet

14:323

5.1.2ServicesProvidedtotheTransport

Layer

■Theservicesshouldbeindependentofthe

routertechnology.

■Thetransportlayershouldbeshielded

fromthenumber,type,andtopologyof

therouterspresent.

■Thenetworkaddressesshouldusea

uniformnumberingplan,evenacross

LANsandWANs.

14:324

5.1.3Implementationof

ConnectionlessService

■Routingwithinadiagramsubnet.

A'stable

initiallylaterC'stableE'stable

A—A—AAAC

BBBBBABD

CCCCC—CC

DBDBDDDD

ECEBEEE—

FCFBFEFF

14:325

Dest.Line

5.1.4ImplementationofConnection-

OrientedServiceI

■Routingwithinavirtual-circuitsubnet.

A'stabletableE'stable

H1：1C!1Aj1C：1F!1

H3：1C\：2A；2C：2F：2

InOut

14:32MultipleLogicLink6

5.1.5ComparisonofVirtual-Circuit

■landDatagramSubnets

IssueDatagramsubnetVirtual-circuitsubnet

CircuitsetupNotneededRequired

AddressingEachpacketcontainsEachpacketcontainsa

thefullsourceandshortVCnumber

destinationaddress

StateinformationRoutersdonotholdEachVCrequiresrouter

stateinformationaboutconnectionstablespaceperconnection

RoutingEachpacketisRoutechosenwhenVC

routedindependentlyissetup;allpackets

followit

EffectofrouterfailuresNone,exceptforpacketsAllVCsthatpassed

lostduringthecrashthroughthefailed

routerareterminated

QualityofserviceDifficultEasyifenoughresources

canbeallocatedin

advanceforeachVC

CongestioncontrolDifficultEasyifenoughresources

canbeallocatedin

14:3advanceforeachVC

5.2RoutingAlgorithms(l)

3■TheOptimalityPrinciple

■ShortestPathRouting

■Flooding

■DistanceVectorRouting

■LinkStateRouting

■HierarchicalRouting

■BroadcastRouting

■MulticastRouting

■RoutingforMobileHosts

■RoutinginAdHocNetworks

14:328

5.2RoutingAlgorithms(2)

■Agoodroutingalgorithm:

■Correctness

■Simplicity

■Robustness

■Stability

■Fairness

■Optimality.

■Nonadaptiveoradaptive(staticor

dynamic)algorithms

14:329

U\5.2.1TheOptimalityPrinciple

I■IfrouterJisontheoptimalpathfromrouterItorouterK,thenthe

optimalpathfromJtoKalsofallsalongthesameroute.

■Sinktree:thesetofoptimalroutesfromallsourcestoagiven

destinationformatreerootedatthedestination

■AsinktreeforrouterB.

■Thegoalofallroutingalgorithmsistodiscoverthesinktrees

14:32

522ShortestPathRouting(l)

■Computingthe

shortestpath

fromAtoD.

■Permanent

node

■Tentatively

labelednode

■Workingnode.

■http:〃carbon./~hgreenbe/sessions/dijkstra/DijkstraApplet.html

14:3211

523Flooding

■Everyincomingpacketissentouton

everyoutgoinglineexcepttheoneit

arrivedon.

■Throwoutduplicatepackets

■Hopcounter

■Tokeeptrackofthefloodedpackets

■Selectiveflooding

■Robust

14:3212

524DistanceVectorRouting(l)

Newestimated

Router

ABD

FG

EH

JKL

(a)

■Distancevectorroutingalgorithms

■Eachroutermaintainatablegiving

thebestknowndistancetoeach810126table

______)

destinationandthelinetogetthere.VforJ

Vectorsreceivedfrom

■ThesetablesareupdatedbyJ'sfourneighbors

exchanginginformationwiththe

(b)

14:32neighbors.13

524DistanceVectorRouting(2)

■Thecount-to-infinityproblem

■Goodnews

■Badnews

ABcDEABCDE

•————•————•————•-—••———•————•————•———•

■■・•Initially1234Initially

1■・•After1exchange3234After1exchange

12・•After2exchanges3434After2exchanges

123•After3exchanges5454After3exchanges

1234After4exchanges5656After4exchanges

7676After5exchanges

(a)7878After6exchanges

■

••••

(b)

14:3214

,5.2.5LinkStateRouting(l)

■Eachroutermustdothefollowing:

■Discoveritsneighbors,learntheirnetworkaddress.

■sendingaHELLOpacketoneachpoint-to-pointline

■Measurethedelayorcosttoeachofitsneighbors.

■Constructapackettellingallithasjustlearned.

■Sendthispackettoallotherrouters.

■Computetheshortestpathtoeveryotherrouter.

14:3215

525LinkStateRouting(2)

■MeasuringLineCost

■SendaECHOpacketthatrequirestheothersideto

sendbackimmediately

■Delaytime:bandwidthorbandwidth+load?

■Oscillations,CForEI

14:3216

・5.2.5LinkStateRouting(3)

F■BuildingLinkStatePacketsperiodicallyor

whensomesignificanteventoccurs

■identityofthesender

■asequencenumber

■age

■alistofneighbors

(a)(b)7

525LinkStateRouting(4)

■Distributing(Flooding)theLinkStatePackets

■Eachpacketcontainsa32bitsequencenumber.

■Routerskeeptrackofallthe(sourcerouter,sequence)

pairsandcheckeveryarrivedstatepacket.

■Ifitisnew,flooding.

■Ifitisaduplicate,discarded.

■Ifapacketwithasequencenumberlowerthanthehighest

oneseensofareverarrives,rejected.

■Age

■Routerdecrementstheageoncepersecond.The

informationwhoseageiszerowilbediscarded.

■decrementedbyeachrouterduringthefloodingprocess

14:3218

525LinkStateRouting(5)

■ComputingtheNewRoutes

■Dijkstra'salgorithm.

■Problem:

■Thememoryrequiredtostoretheinputdata

andallrouteinformationforeveryrouter

■Someerroronarouterwillinfluenceall

network

14:3219

M|5,2,6HierarchicaIRouting

Fulltablefor1AHierarchicaltablefor1A

Dest.LineHopsDest.LineHops

Region1Region21A————

/k市'、、/'2A2Er\1B1B11B1

1C1C11C1

1

IAV9Hi------------m\9!'

(2・Q・Q2A1B21B2

\1G，\2C2DZ

，、、___,2B1B31C2

2C1B31C3

2D1B41C4

3A1C3

3B1C2■Asintelephonenetwork,

4A1C3

4B1C4Region

Region3Region4Region5

4C1C4

5A1C4■Routerknowingallthedetails

5B1C5withinitsownregion,but

5C1B5

5D1C6knowingnothingaboutother

5E1C5崎

(a)(b)regio

■Increasedpathlength

■Howmanylevelsshouldthe

14:32hierarchyhave?20

M5.2.7BroadcastRouting(1)

^1■SpecialApplication

■Sendingapackettoalldestinationssimultaneously

■Broadcastingmethod

■Simplysendadistinctpackettoeachdestination

■Flooding

■Multidestinationrouting

■Eachpacketcontainsalistofdestinations,therouterchecksittodetermine

thesetofoutputlinesthatwillbeneeded.

■Foreachoutputlinetheroutergeneratesanewcopyofthepacket

includingonlythosedestinationsthataretousetheline.

■Spanningtree,routercopyanincomingbroadcastpacketontoall

thespanningtreelines

■Reversepathforwarding,routerchecksifthepacketarrivedon

thelinethatisnormallyusedforsendingpacketstothesourceof

thebroadcast

14:3221

527BroadcastRouting(2)

BC

AD

F

E

G

J

H

K

M

(a)(b)(c)

■Reversepathforwarding.

■(a)Asubnet.

■(b)Fssinktree.

i4：32■(c)Thetreebuiltbyreversepathforwarding.22

528MulticastRouting(l)

'I.Group

■MulticastorBroadcast

■Groupmanagement.Createanddestroygroups,joinandleavegroups

■Senderandreceiver.

■Routersknowwhichoftheirhostsbelongtowhichgroups.

■BasedonSpanningtree

■Eachroutercomputesaspanningtreecoveringallotherrouters

■Therouterexaminesitsspanningtreeandprunesit,removingalllinesthatdo

notleadtohoststhataremembersofthegroup.

■Multicastpacketsareforwardedonlyalongtheappropriatespanningtree.

■EachroutershouldstoreatotalofM*Ntrees(NgroupsandMmembers)

■Sharingtree

■therootnearthemiddleofthegroup.

■Sourcessendsmessagetotheroot,whichthendoesthemulticastalongthe

spanningtree.

■Onegrouponetree

14:3223

MulticastRouting(2)

(a)(b)

Anetwork.Aspanningtreefortheleftmostrouter.

24

14：32Amulticasttreeforgroup1.Amulticasttreeforgroup2.

■529RoutingforMobileHosts(l)

■Basicgoals:=

■Allhigher-layerconnectionsshouldsurvivetheaddresschange

■Mobilehostshouldbereachableaslongasitisconnectedtothe

Internetsomewhere.

■Amodel

■aWANtowhichLANs,MANs,andwirelesscellsareattached.

■HomeLocation/ForeignAgent

ForeignLAN

14:32WAN25

MAN

529RoutingforMobileHosts(2)

MobileNode(MN):anodewhichcanchangeitslocationwhile

maintaininganyongoingcommunicationsandusingonlyits

home(permanent)IPaddress.

HomeAgent(HA):arouterwithatleastoneinterfaceonthe

MN'shomelinkwhich:

■MNkeepsinformedofitscurrentlocation,i.e.,itscare-of-address(COA)

■InterceptspacketsdestinedtotheMN'shomeaddressandtunnelsthemto

theMN'scurrentlocation(orCOA).

ForeignAgent(FA):arouteronaforeignlinkwhich:

■AssiststheMNininformingitsHAofitscurrentCOA

■Sometimes,providesaCOAandde-tunnelspacketsfortheMN

■ActsasthedefaultrouterforpacketsgeneratedbytheMNwhileconnected

tothisforeignlink

Care-ofaddress(COA)

■UsedbyaMNwhileitisattachedtoaforeignlink.TheassociationofaCOA

withahomeaddressforamobilenodeisknownasabinding.

14:3226

,5.2.9RoutingforMobileHosts(3)

'■Registrationprotocol

■Periodically,eachforeignagentbroadcastsapacket

announcingitsexistenceandCOA.

■Themobilehostregisterswiththeforeignagent,

givingitshomeaddress,currentdatalinklayer

address,andsomesecurityinformation.

■Theforeignagentcontactsthemobilehostshome

agent:OneofyourhostsisoverhereanditsCOA.

■Thehomeagentexaminesthesecurityinformation

andacknowledgement

■Foreignagentgetstheacknowledgementandinforms

themobilehostthatitisnowregistered.

14:3227

529RoutingforMobileHosts(4)

■Packetroutingformobileusers.

Correspondent.

node

1.Packetissenttothe

mobilehostshomeaddressHome

Agent

4.Subsequentpacketsare

tunneledtotheforeignagent

3.Senderisgivenforeign

agentsaddress

ForeignAgent2.Packetistunneedtothe

foreignagent

MN

14:3228

,5.3CongestionControlAlgorithms

■GeneralPrinciplesofCongestionControl

■CongestionPreventionPolicies

■CongestionControlinVirtual-CircuitSubnets

■CongestionControlinDatagramSubnets

■LoadShedding

■JitterControl

14:3229

CongestionDefinition

■Whentoomuchtrafficisoffered,congestionsetsin

andperformancedegradessharply.

■toachievehighutilization,lowqueueingdelayand

loss,fairness,andstability.

Perfect

Maximumcarrying

p

①capacityofsubnet

Q一

>Desirable

opj

s

o/Congested

专

d

14:3230

Packetssent

■Resource(linkbandwidthandbufferspace)vs.load

■Sourcescancreateademandfornetworkresourceshigher

thanthenetworkcanhandleatacertainlink.

■Thebufferintheroutersoffersofprotectionagainstan

increaseintrafficarrivalrate.

■Ifthebufferspaceisexhausted,therouterhastostart

droppingpackets.

■Toomuchbufferspacenbemoreharmfulthantoolittle,

becausethepacketswillhavetobedroppedonlyafterthey

haveconsumedvaluablenetworkresources.

■localvs.global

■Flowcontrolvs.Congestioncontrol

■Flowcontrolisonlyonemethodofthecongestioncontrol.

14:3231

5.3.1GeneralPrinciplesof

M|CongestionControI

■1Openloopandclosedloop

■Openlooptosolvetheproblembygooddesign,make

decisionswithoutregardtothecurrentstateofthenetwork.

■Senderdescribesitsratetothenetworkwithparameterslike

burstsizeandinterburstinterval.

■Closedlooparebasedonafeedbackloop.

■Monitorthesystem,detectwhenandwherecongestionoccurs.

Implicit:theend-hostsmonitortheirown

transmissions(delay,loss)

Explicit:congestioninfo,canbecarriedin

protocolheadersexplicitly

■Passinformationtowhereactioncanbetaken.

■Adjustsystemoperation.

14:3232

5.3.1GeneralPrinciplesof

CongestionControl(2)

■Increasetheresources

■Decreasetheload.

■Selectingwhichpacketstodrop

■Determiningwhenthisisappropriate.

■Limitingnewdataflow

14:3233

5.3,2CongestionPreventionPolicies

■Policiesthataffectcongestion.

LayerPolicies

Transport•Retransmissionpolicy

•Out-of-ordercachingpolicy

•Acknowledgementpolicy

•Flowcontrolpolicy

•Timeoutdetermination

Network•Virtualcircuitsversusdatagraminsidethesubnet

•Packetqueueingandservicepolicy

•Packetdiscardpolicy

•Routingalgorithm

•Packetlifetimemanagement

Datalink•Retransmissionpolicy

•Out-of-ordercachingpolicy

•Acknowledgementpolicy

•Flowcontrolpolicy

14:3234

5.3.3CongestionControlinVirtual-

■circuitSubnets

F■Admissioncontrol

■SetupnewVCbutavoidingproblemareas.

■Negotiateanagreementbetweenthehostand

subnet

14(a)(b)

5.3.4CongestionControlin

・DatagramSubnets(1)

■Monitortheutilizationofitsoutputlines

■U,therecentutilizationofthatline.

■f,instantaneouslineutilization,(either0or1),

■a,constantdetermineshowfasttherouterforgetsrecenthistory

■Unew=alloid+(l-a)f

■Warningstate,whenIImovesabovethethreshold

■WarningBit

■Setinthepacketsheadwhenintowarningstate.

■Destinationcopiedthebitintothenextacknowledgement.

■Thesourcethencutbackontraffic.

■Aslongasthewarningbitscontinuedtoflowin,thesource

continuedtodecreaseitstransmissionrate.

14:3236

5.3.4Congestion

ControlinDatagram

Subnets(2)

■Hop-by-HopChoke

Packets

■Achokepacketthat

affectsonlythesource.

■AchokepacketthatReduced

flow

affectseachhopit

passesthrough.

14:32

(a)(b)

Ml5,3,5LoadShedding(2-1)

■Justthrowthemaway

■Taildrop,hasservedtheInternetwellforyears,but

■itsustainsfullqueuesandcancauselockout

■Drop-from-front,improvestheperformanceby

allowingtheurgentsignal(congestion...)toreach

sourcefaster

■Random-drop,istonotifythoseuserswhosetraffic

contributesmoretothecongestion.

14:3238

5.3.5LoadShedding(2-2)

■Dependontheapplications,WineorMilk

■Priority,somepacketsaremoreimportantthan

others

■Allowhoststoexceedthelimits,butallexcess

trafficbemarkedaslowpriority

■RED(RandomEarlyDetection)

■Discardingpacketsbeforeallthebufferspaceis

exhausted

■Threshold

■Tothrowpacketsrandomly

14:3239

,5.3.6JitterControl(2-1)

Packetdepartssource12345678

Packetarrivesatbuffer12345678

■Jitter:variationinthepacketarrivaltimes

■Highjitter.

■Lowjitter.sS

oE

S

-BsB

dd

oo

uU

。O

二

0。S

Highjitter

LLLLLowjitter

MinimumDelay-----►Delay

delay

(dueto

14:32speedof

light)(a)(b)

■5.3,6JitterControl（2-2）

、■Interactivereal-timestreams

■Teleconferencing,Remotecontrols,Games

Routerholdsorsendsquicklythepackets.Twoproblems

Overflow:bufferisfull,mustreleasepacketsbeforetheirduetime

Underflow:bufferisempty,packettobereleasedhasn'tarrived

yet

Switch

Incoming

packets

41

14:32Nopacketlossorreordering

Ml5,4QualityofService

■Requirements

■TechniquesforAchievingGoodQualityof

Service

■IntegratedServices

■DifferentiatedServices

-LabelSwitchingandMPLS

■TrafficEngineering

14:3242

■[541Requirements

ApplicationReliabilityDelayJitterBandwidth

E-mailHighLowLowLow

FiletransferHighLowLowMedium

WebaccessHighMediumLowMedium

RemoteloginHighMediumMediumLow

AudioondemandLowLowHighMedium

VideoondemandLowLowHighHigh

TelephonyLowHighHighLow

VideoconferencingLowHighHighHigh

14:3243

5.4.2TechniquesforAchieving

GoodQualityofService

■Avarietyoftechniquesdeveloped

■Overprovision

■Buffering

■Trafficshaping