ch3分組交換網(wǎng)絡(luò)

2

Chapter3.PacketSwitchingNetworks

SwitchingandForwarding

VirtualCircuitandDatagramNetworks

ATMandCellSwitching

X.25andFrameRelay

Routing

What’sInsideaRouter/Switch?

InsideaSwitch:ArchitectureOverview

Twokeyswitchfunctions:

Runroutingalgorithms/protocol

Forwardingpacketsfromincomingtooutgoinglink

forwardingdataplane(hardware)

forwardingtablescomputed,pushedtoinputports

routing,management

controlplane(hardware&software)

4

InputPortFunctions

Physicallayer:

Bit-levelreception

Datalinklayer:

Errorhandling

Decentralizedswitching

Lookupoutputportusingforwardingtable

Completeinputportprocessingat“l(fā)inespeed”

Queuing:ifpacketsarrivefasterthanforwardingrateintoswitchfabric

ThreeTypesofSwitchingFabrics

Transferpacketfrominputbuffertoappropriateoutputbuffer

Switchingrate:rateatwhichpacketscanbetransferfrominputstooutputs

oftenmeasuredasmultipleofinput/outputlinerate

Ninputs:switchingrateNtimeslineratedesirable

crossbar

Threetypesofswitchingfabrics

memory

memory bus

SwitchingviaMemory

Firstgenerationrouters:

TraditionalcomputerswithswitchingunderdirectcontrolofCP

Packetcopiedtosystem’smemory

memory

Speedlimitedbymemorybandwidth(2buscrossingsperdatagram)

inputport(e.g.,Ethernet)

outputport(e.g.,Ethernet)

systembus

SwitchingviaaBus

Datagramfrominputportmemorytooutputportmemoryviaasharedbus

Buscontention:switchingspeedlimitedbybusbandwidth

32Gbpsbus,Cisco5600:sufficientspeedforaccessandenterpriserouters

bus

SwitchingviaaMesh

Overcomebusbandwidthlimitations

crossbar

Banyannetworks,crossbar,otherinterconnectionnetsinitiallydevelopedtoconnectprocessorsinmultiprocessor

Advanceddesign:fragmentingdatagramintofixedlengthcells,switchcellsthroughthefabric.

Cisco12000:switches60Gbpsthroughtheinterconnectionnetwork

OutputPortFunctions

Buffering

Datagram(packets)canbelostduetocongestion,lackofbuffers

Requiredwhenpacketsarrivefromfabricfasterthanthetransmissionrate

Choosesamongqueuedpacketsfortransmission

Selectpacketstodropwhenbuffersaturates

Priorityscheduling–whogetsbestperformance

Schedulingdiscipline

Routing

Routing

Objective

Buildroutingtablesonswitchesfordatagramnetworks

ChoosepathsandbuildforwardingtableswhensettingupconnectionsforVCnetworks

Characteristicsrequired

Efficiency:e.g.smallestpossiblelineorswitch

Resilience:peakload,switchorlinefailure

Stability:avoidoscillation

NetworkAbstraction

RoutingElements

Performancecriteria

Decisiontime

Decisionplace

Networkinfosource

Networkinfoupdatetiming

PerformanceCriteria

Minimumhop

e.g.1–3–6

Leastcost

e.g.1–4–5–6

Determinecost

Minimumdelay:queuelength

Largestthroughput:reverseoftransmissionrate

DecisionTimeandPlace

Time

Foreachpacket---datagramnetworks

Atthestartofeachvirtualcircuit---VCnetworks

Place

Centralized

Source---sourcerouting

Distributed---byeachswitchnode

NetworkInfoSourceandUpdateTiming

Infosource

Localinformation

Adjacentswitches

Allswitchesinthenetwork

Updatetiming

Updateperiodically

Uponmajorchangesinswitchesorlinks

Fixed(manualconfiguration)

DifferentRoutingStrategies

Central(static)

Fixedandconfigured

Distributed

Flooding

Random

Adaptive

CentralRouting

Singlefixedrouteforeachsourcetodestinationpair

Determineroutesusingaleastcostalgorithm

Routesre-configuponmajorchangesinnetworktopology

1 6

Centralized

Distributed

FixedRoutingTables

20

Flooding

Nonetworkinforequired

Packetsentbyswitchtoeveryneighbor

Packetsretransmittedoneverylinkexceptincominglink

Eventuallyanumberofcopieswillarriveatdestination

Duplicates

Manycopiesofthesamepacketiscreated

Cycleproblem

Thesecopiesmaycirclingaroundthenetworkforever

21

Ahopcountinpacketscanhandletheproblem

FloodingExample

Hopcount=3

Initial

3packets

1sthop

9packets

2ndhop

23packets

22

PropertiesofFlooding

Allpossibleroutesaretried

Veryrobust

Atleastonepacketwilltakeminimumcostroute

Canbeusedtosetupvirtualcircuit

Allswitchesarevisited

Usefultodistributeinformation(e.g.routing)

RandomRouting

Nodeselectsoneoutgoingpathforretransmissionofincomingpacket

Selectioncanberandomorroundrobin

Orbasedonprobabilitycalculation

Nonetworkinfoneeded

Suitableforstrongly-connectednetwork

Routeistypicallynotoptimal

AssignProbabilities

Pi=Ri/jRj

Pi–Probabilityofselectingout-linki

Ri–Costfactoroflinki

Possiblecostfactor

Transmissionrate–forthroughput

Reverseofqueuesize–fordelay

AdaptiveRouting

Usedbyalmostallpacketswitchingnetworks

Routingdecisionschangeasconditionsonthenetworkchange

Requiresinfoaboutnetwork

Tradeoffbetweenqualityofnetworkinfoandoverhead

Aidincongestioncontrol

AnIsolatedAdaptiveRouting

Onlylocalinfoused

Strategy1:routetotheoutgoinglinkwithshortestqueuelengthQ

Pros.Loadbalancing

Cons.Mayawayfromthedestination

Strategy2:takedirectionintoaccount

EachlinkhasabiasBforthedestination

RoutetominimizeQ+B

=11

=9

Q+B=1+3=4

=5

27

2LeastCostAlgorithms

Foreachpairofnodes,findapathwiththeleastcost

Dijkstra’sAlgorithm

Bellman-FordAlgorithm

Dijkstra’sAlgorithm

Findshortestpathsfromgivensourcetoallothernodes

Developingpathsinorderofincreasingpathcost(length)

Denote

N=setofnodesinthenetwork

s=thesourcenode

T=setofnodessofarincorporatedbythealgorithm

w(i,j)=linkcostfromnodeitonodej

w(i,i)=0

w(i,j)=ifthetwonodesarenotdirectlyconnected

w(i,j)>0ifthetwonodesaredirectlyconnected

Dijkstra’sAlgorithmMethod

L(n)=costofleast-costpathfromsourcestonoden

currentlyknown

Attermination,L(n)iscostofleast-costpathfromston

Step1[Initialization]

T={s}setofnodesincorporatedconsistsofonlysourcenode

L(n)=w(s,n) forns

Initialpathcoststoneighboringnodesaresimplylinkcosts

Step2[GetNextNode]

FindnodexnotinTwithleast-costpathfroms(i.e.minL(x))

IncorporatenodexintoT

AlsoincorporatetheedgethatlinksxwiththenodeinTthatcontributestothepath

Dijkstra’sAlgorithmMethod

Step3[UpdateLeast-CostPaths]

L(n)=min[L(n),L(x)+w(x,n)]forallnT

Iflattertermisminimum,pathfromstonispathfromstox

concatenatedwithlinkfromxton

AlgorithmterminateswhenallnodeshavebeenaddedtoT

Dijkstra’sAlgorithmNotes

Oneiterationofsteps2and3addsonenewnodetoT

Definesleastcostpathfromstothatnode

ValueL(n)foreachnodenisthecost(length)ofleast-costpathfromston

Atlast,Tdefinestheleast-costpathfromstoeachothernode

ExampleofDijkstra'sAlgorithm

ResultsofExampleDijkstra’sAlgorithm

No

T

L(2)

Path

L(3)

Path

L(4)

Path

L(5)

Path

L(6)

Path

1

{1}

2

1-2

5

1-3

1

1-4

–

–

2

{1,4}

2

1-2

4

1-4-3

2

1-4-5

–

3

{1,2,4}

4

1-4-3

2

1-4-5

–

4

{1,2,4,5}

3

1-4-5-3

4

1-4-5-6

5

{1,2,3,4,5}

4

1-4-5-6

6

{1,2,3,4,5,6}

2

1-2

3

1-4-5-3

1

1-4

2

1-4-5

4

1-4-5-6

Destination

Next-Hop

Distance

2

2

2

3

4

3

4

4

1

5

4

2

6

4

4

Dijkstra’salgorithmdiscussion

algorithmcomplexity:nnodes

eachiteration:needtocheckallnodes,w,notinN

n(n+1)/2comparisons:O(n2)

moreefficientimplementationspossible:O(nlogn)

oscillationspossible:

1+e

e

e.g.,supportlinkcostequalsamountofcarriedtraffic:

2+e

1+e1

2+e

1+e

2+e

1+e1

initially

giventhesecosts,findnewrouting….

resultinginnewcosts

giventhesecosts,findnewrouting….resulting

innewcosts giventhesecosts,find

newrouting….resultinginnewcosts

Bellman-FordAlgorithm

Findshortestpathsfromgivennodecontainingatmost1link

Findtheshortestpathsthatcontainingatmost2links,basedontheresultof1link

Findtheshortestpathsof3linksbasedonresultof2links,andsoon

s=thesourcenode

w(i,j)=linkcostfromnodeitonodej

w(i,i)=0

w(i,j)=ifthetwonodesarenotdirectlyconnected

w(i,j)>0ifthetwonodesaredirectlyconnected

Bellman-FordAlgorithmMethod

h=maximumnumberoflinksinpathatcurrentstageofthealgorithm

Lh(n)=costofleast-costpathfromstonunderconstraintofnomorethanhlinks

Step1[Initialization]

L0(n)=,forallns

L1(n)=w(s,n)

Lh(s)=0,forallh

Bellman-FordAlgorithmMethod

Step2[Update]

Foreachsuccessiveh>0

Foreachns,computeLh+1(n)=minj[Lh(j)+w(j,n)]

Connectnwithpredecessornodejthatachievesminimum

Eliminateanyconnectionofnwithdifferentpredecessorformedduringearlieriterations

Repeatuntilnochangemadetoroute

(convergence)

Bellman-FordAlgorithmNotes

Foreachiterationwithhandforeachdestinationnoden

Comparesnewlycomputedpathfromstonoflengthhwithpathfrompreviousiteration(h1)

Ifpreviouspathshorteritisretained

Otherwisenewpathisdefined

ExampleofBellman-FordAlgorithm

40

ResultsofBellman-FordExample

h

Lh(2)

Path

Lh(3)

Path

Lh(4)

Path

Lh(5)

Path

Lh(6)

Path

0

–

–

–

–

–

1

2

1-2

5

1-3

1

1-4

–

–

2

4

1-4-3

2

1-4-5

10

1-3-6

3

3

1-4-5-3

4

1-4-5-6

4

2

1-2

3

1-4-5-3

1

1-4

2

1-4-5

4

1-4-5-6

Destination

Next-Hop

Distance

2

2

2

3

4

3

4

4

1

5

4

2

6

4

4

Dijkstravs.Bellman-Ford

RoutingbasedonDijkstra

Linkstatesfloodtoallothernodes

Eachnodewillhavecompletetopologyandbuilditsownroutingtable

RoutingbasedonBellman-Ford

Eachnodemaintaindistancevectorstootherknownnodes

Vectorsexchangedwithdirectneighbourstoupdatethepathsandcosts

Routingtablesbuiltinadistributedway

L(n)=min[L(n),L(x)+w(x,n)]

Lh(x,D)

S … D S D

Dijkstra’s(LinkState)

Bellman-Ford(DistanceVector)

Dijkstravs.Bellman-Ford

Messagecomplexity

DK:nnodes,elinks,O(ne)

messages

BF:Dependsonconvergencetime

Speedofconvergence

DK:O(n2)andquick;Mayhaveoscillations

BF:Slowanddependsonchanges;

44

Maycontainroutingloops

Robustness:whathappensifnodemalfunctions

DK:Advertiseincorrectdirectlinkscost;

Errorrangeconstrained

BF:Errornodecanexchangeincorrectpathscost;

Errormaypropagatethroughthenetwork

Routingalgorithmclassification

Q:globalorlocalinformation?centralized:

allroutershavecompletetopology,linkcostinfo

“l(fā)inkstate”algorithms

decentralized:

routerknowsphysically-connectedneighbors,linkcoststoneighbors

“distancevector”algorithms

iterativeprocessofcomputation,exchangeofinfowithneighbors

Q:staticordynamic?

static:

routeschangeslowlyovertime

dynamic:

routeschangemorequickly

periodicupda