FundamentalQoSRoutingExperiment基本的QS路由實(shí)驗(yàn)6、法律的基礎(chǔ)有兩個(gè)，而且只有兩個(gè)……公平和實(shí)用?！?、有兩種和平的暴力，那就是法律和禮節(jié)。——歌德8、法律就是秩序，有好的法律才有好的秩序?！獊喞锸慷嗟?、上帝把法律和公平湊合在一起，可是人類卻把它拆開?！椤た茽栴D10、一切法律都是無(wú)用的，因?yàn)楹萌擞貌恢鼈儯鴫娜擞植粫?huì)因?yàn)樗鼈兌兊靡?guī)矩起來(lái)。——德謨耶克斯FundamentalQoSRoutingExperiment基本的QS路由實(shí)驗(yàn)FundamentalQoSRoutingExperiment基本的QS路由實(shí)驗(yàn)6、法律的基礎(chǔ)有兩個(gè)，而且只有兩個(gè)……公平和實(shí)用?！?、有兩種和平的暴力，那就是法律和禮節(jié)?！璧?、法律就是秩序，有好的法律才有好的秩序?！獊喞锸慷嗟?、上帝把法律和公平湊合在一起，可是人類卻把它拆開。——查·科爾頓10、一切法律都是無(wú)用的，因?yàn)楹萌擞貌恢鼈?，而壞人又不?huì)因?yàn)樗鼈兌兊靡?guī)矩起來(lái)?！轮円怂?006QoSRoutingandForwardingBenefitsofQoSRoutingWithoutQoSrouting:mustprobepath&backtrack;nonoptimalpath,controltrafficandprocessingOH,latencyWithQoSrouting:optimalroute;“focusedcongestion”avoidanceefficientCallAdmissionControl(atthesource)efficientbandwidthallocation(pertrafficclass)resourcerenegotiationeasier2006

QoSRoutingandForwarding

BenefitsofQoSRoutingWithoutQoSrouting:mustprobepath&backtrack;nonoptimalpath,controltrafficandprocessingOH,latencyWithQoSrouting:optimalroute;“focusedcongestion”avoidanceefficientCallAdmissionControl(atthesource)efficientbandwidthallocation(pertrafficclass)resourcerenegotiationeasierMultipleConstraintsQoSRoutingGiven:-a(realtime)connectionrequestwithspecifiedQoSrequirements(e.g.,Bdw,Delay,Jitter,packetloss,pathreliability,etc)Find:-amincost(typicallyminhop)pathwhichsatisfiessuchconstraints-ifnofeasiblepathfound,rejecttheconnection

ExampleofQoSRouting

2HopPath-->Fails(Totaldelay=55>25andMinBW=20<30)

3HopPath-->Succeeds(Totaldelay=24<25,MinBW=90>30)

5HopPath-->Donotconsider,although(TotalDelay=16<25,

MinBW=90>30)ABD=30,BW=20D=25,BW=55D=5,BW=90D=3,BW=105D=5,BW=90D=1,BW=90D=5,BW=90D=2,BW=90D=5,BW=90D=14,BW=90Constraints:Delay(D)<=25,AvailableBW>=30Welookforfeasiblepathwithleastnumberofhops

TheComponentsofQoSRoutingQ-OSPF:linkstatebasedprotocol;itdisseminateslinkstateupdates(includingQoSparameters)toallnodes;itcreates/maintainsglobaltopologymapateachnodeOSPF(OpenShortestPathFirst):forintra-ASroutingisalink-stateprotocolthatusesfloodingoflinkstateinformationandaDijkstraleastcostpathalgorithmToreplacetheDijkstraalgorithmusingBellman-Fordconstrainedpathcomputationalgorithm:itcomputesconstrainedminhoppathstoalldestinationsateachnodebasedontopologymapCallAcceptanceControl(CAC)PacketForwarding:sourcerouteorMPLSOSPFOverview5MessageTypes1)“Hello”-letsanodeknowwhotheneighborsare2)LinkStateUpdate-describessender’scosttoitsneighbors3)LinkStateAck.-acknowledgesLinkStateUpdate4)Databasedescription-letsnodesdeterminewhohasthemostrecentlinkstateinformation5)LinkStateRequest-requestslinkstateinformationOSPFOverview(cont)ABCDE1122233“LinkStateUpdateFlooding”O(jiān)SPFOverview(cont)“Hello”messageissentevery10secondsandonlybetweenneighboringroutersLinkStateUpdateissentevery30minutesoruponachangeinacostofapathLinkStateUpdateistheonlyOSPFmessagewhichisacknowledgedRoutersonthesameLANuse“DesignatedRouter”schemeImplementationofOSPFinQoSSimulator

LinkStateUpdateissentevery2secondsNoackisgeneratedforLinkStateUpdatesLinkStateUpdatemayinclude(forexample):-Queuesizeofeachoutgoingqueue(averagedover10sslidingwindow)-Throughputoneachoutgoinglink(averagedover10sslidingwindow)-Totalbandwidth(capacityofthelink)Sourceroutercanuseaboveinformationtocalculate-end-to-enddelay,-availablebuffersize,-availablebandwidthBellman-FordAlgorithm(withdelay)11012423212435BellmanEquation:jDih+1Dh=min[d(i,j)+]1312435D11=0D21=1D31=3D41=00D51=00onehop1312435D12=0D22=1D32=2D42=11D52=51012twohopsiDhhDh*threehops112435D13=0D23=1D33=2D43=7D53=41223B/FAlgorithmPropertiesMC(multipleconstraints)BellmanFordalgorithmreplacestheDijkstraalgorithmofconventionalOSPFimplementationsB/FslightlylessefficientthanDijkstra(O(NxN)insteadofO(NlgN))However,B/Fgeneratessolutionsbyincreasinghopdistance;thus,thefirstfoundfeasiblesolutionis“hop”optimal(ie,minhop)PolynomialperformanceformostcommonsetsofMC(multipleconstraintse.g.bandwidthanddelay)CACandPacketForwarding

CAC:iffeasiblepathnotfound,callisrejected;alternatively,sourceisnotifiedofconstraintviolation,andcanresubmitwithrelaxedconstraint(callrenegotiation)Packetforwarding:(a)sourcerouting(perflow)(b)MPLS(perclass)ApplicationI:IPTelephonyM-CACatsource;nobandwidthreservationalongpath36node,highlyconnectednetworkTrunkcapacity=15MbpsNonuniformtrafficrequirementTworoutingstrategiesarecompared:Minhoprouting(noCAC)QoSrouting

Simulationplatform(UCLA):PARSECwirednetworksimulation(QualNet)0121854213630241487131716101115919262734282220212333352925313250Km15Mbit/secQoSSimulator:VoiceSourceModelingSILENCETALK1/=352ms1/=650msVoiceconnectionrequestsarriveaccordingtoaPoissonprocess,oratfixedintervalsOnceaconnectionisestablished,thevoicesourceismodeledas2stateMarkovchain1voicepacketevery20msduringtalkstateSimulationParameters10MinuteSimulationRunsEachvoiceconnectionlasts3minutesOSPFupdatesaregeneratedevery2seconds(30minuteOSPFupdateintervalinMinhopscheme)Newvoiceconnectionsgeneratedwithfixedinterarrival(150ms)MeasurementsareinSteady-state(after3minutes)100msecdelaythreshold3Mbit/secbandwidthmarginoneachtrunkThecandidatesourcedestinationpairsare:(8,20),(0,34),(3,32),(4,32),(5,32),(10,32),(16,32)MinhopRoutingWenotethattheratefromthe5sources(3,4,5,10,16)intodestination32is4.76calls/sec,exceedingtheprocessingcapacityofasinglepathwhichis3.2inMinHopand2.6inMCBFMinhopRouting(cont.)Thesource-destinationpairs(0,34)and(8,20)aregettingalloftheircallsthroughwithzerolossandend-to-enddelaysbelow100msthreshold.Thisisbecausetheyenjoyexclusiveuseofminhoppaths(0,1,18,19,25,24,34)and(8,14,20),respectivelyTheremainingsourcedestinationpairs(3,32),(4,32),(5,32),(10,32),and(16,32)donotevengetasinglepacketthroughwithdelaybelow100msecthreshold.Moreover,theysufferheavyloss.Thereasonisverysimple:theyallshareacommonsubpath(9,8,2,32)andthuscompeteforthesamebottleneck0121854213630241487131716101115919262734282220212333352925313250Km15Mbit/secMINHOPROUTINGQoSRoutingMCBellman-FordroutingalgorithmmanagestobalancetheloadonalternatepathsInfact,twoalternatepathsareusedtoroutethetrafficoriginatingfromthe5sources0121854213630241487131716101115919262734282220212333352925313250Km15Mbit/secQoSROUTING0121854213630241487131716101115919262734282220212333352925313250Km15Mbit/secQoSROUTINGPreliminaryAnalysisTheQoSroutingacceptsalltheofferedcallsbyspreadingtheloadonalternatepaths100.0%36.88%100.0%%ofpacketsbelow100ms0.0%51.34%0.0%%ofpacketsabove100ms0.0%11.78%0.0%%ofpacketslost187527622762#voicecallsacceptedinsteadystate279027622762#voicecallsattemptedinsteadystateMinhopw/CACMinhopQoSRouting

OSPFpacketsizewas350bytesOSPF(LSA)updatesweregeneratedevery2secondsMeasurementswereperformedona“perfectsquaregrid”topology75msvoicecallgenerationrateApplicationII:MPEGVideoRes.All.CACRSVPtypesignalingrequiredEffectivebandwidth&bufferreservations36nodegrid-typetopologyTrunkcapacity=5.5MbpsInputs=MeasuredMPEGtracesQoSguarantees:no-loss;delay<TmaxSimulationplatform:PARSECwirednetworksimulation(QualNet)APPLICATIONORDERSOURCENODEDESTINATIONNODEPATHCACY/NREJECTIONNODE103511819202122282935Y

224132519201413Y

319202531322620Y

411818Y

53435282935Y

6

1821

192021N19178142021Y

72935NOPATHFOUND

891887118N1814201918Y

92721262021N20262014891521Y

10222828Y

11222821201925243428Y

SIMULATIONRESULTSBandwidth/link:5.5MbpsunidirectionalTmax:0.1sEffectivebandwidth:2.6MbpsEffectivebuffer:260KB(nobuffersaturation)0121854213630241487131716101115919262734282220212