Berkeley ELENG 122 - Intra-domain routing - D1681813

Home> Schools> University of California, Berkeley> Electrical Engineering (ELENG) > ELENG 122> Intra-domain routing

DOC PREVIEW

Berkeley ELENG 122 - Intra-domain routing

School name University of California, Berkeley

Course Eleng 122- Introduction to Communication Networks

Pages 7

This preview shows page 1-2 out of 7 pages.

Save

View full document

Premium Document

Do you want full access? Go Premium and unlock all 7 pages.

Access to all documents

Download any document

Ad free experience

Subscribe for instant access Get instant access

View full document

Premium Document

Do you want full access? Go Premium and unlock all 7 pages.

Access to all documents

Download any document

Ad free experience

Subscribe for instant access Get instant access

Premium Document

Do you want full access? Go Premium and unlock all 7 pages.

Access to all documents

Download any document

Ad free experience

Subscribe for instant access Get instant access

Unformatted text preview:

1EE122:Intra-domainroutingIonStoicaSeptember30,2002(*thispresentationisbasedontheon-lineslidesofJ.Kurose&K.Rose)[email protected] 2InternetRoutingInternetorganizedasatwo levelhierarchyFirstlevel– autonomoussystems(AS’s)- AS– regionofnetworkunderasingleadministrativedomainAS’srunanintra-domainroutingprotocols- DistanceVector,e.g.,RIP- LinkState,e.g.,OSPFBetweenAS’srunsinter-domainroutingprotocols,e.g.,BorderGatewayRouting(BGP)- Defactostandardtoday,BGP-4[email protected] 3ExampleAS-1AS-2AS-3InteriorrouterBGP[email protected] 4Intra-domainRoutingProtocolsBasedonunreliabledatagramdeliveryDistancevector- RoutingInformationProtocol(RIP),basedonBellman-Ford- Eachneighborperiodicallyexchangereachabilityinformationtoitsneighbors- Minimalcommunicationoverhead,butittakeslongtoconverge,i.e.,inproportiontothemaximumpathlengthLinkstate- OpenShortestPathFirstProtocol(OSPF),basedonDijkstra- Eachnetworkperiodicallyfloodsimmediate reachabilityinformationtootherrouters- Fastconvergence,buthighcommunicationandcomputation[email protected] 5RoutingGoal:determinea“good”paththroughthenetworkfromsourcetodestination- GoodmeansusuallytheshortestpathNetworkmodeledasagraph- Routersnodes- Linkedges• Edgecost:delay,congestionlevel,…[email protected] 6ALinkStateRoutingAlgorithmDijkstra’salgorithmNettopology,linkcostsknowntoallnodes- Accomplishedvia“linkstatebroadcast”- Allnodeshavesame infoComputeleastcostpathsfromonenode(‘source”)toallothernodesIterative:afterk iterations,knowleastcostpathtokclosestdestinationsNotationsc(i,j): linkcostfromnodeitoj;costinfiniteifnotdirectneighborsD(v): currentvalueofcostofpathfromsourcetodestinationvp(v): predecessornodealongpathfromsourcetov,thatisnexttovS: setofnodeswhoseleastcostpathdefinitively[email protected] 7Dijsktra’s Algorithm1Initialization:2S={A};3forallnodesv4ifv adjacenttoA5thenD(v)=c(A,v);6elseD(v)=;78Loop9findwnotinSsuchthatD(w)isaminimum;10addwtoS;11updateD(v)forallvadjacenttowandnotinS:12D(v)=min(D(v),D(w)+c(w,v));13//newcosttoviseitheroldcosttovorknown14//shortestpathcosttowpluscostfromwtov15untilallnodesinS;∞[email protected] 8Example: Dijkstra’s AlgorithmStep012345startSAD(B),p(B)2,AD(C),p(C)5,AD(D),p(D)1,AD(E),p(E)D(F),p(F)AEDCBF2213112535∞∞[email protected] 9Example: Dijkstra’s AlgorithmStep012345startSAADD(B),p(B)2,AD(C),p(C)5,A4,DD(D),p(D)1,AD(E),p(E)2,DD(F),p(F)AEDCBF2213112535∞∞∞[email protected] 10Example: Dijkstra’s AlgorithmStep012345startSAADADED(B),p(B)2,AD(C),p(C)5,A4,D3,ED(D),p(D)1,AD(E),p(E)2,DD(F),p(F)4,E∞∞∞[email protected] 11Example: Dijkstra’s AlgorithmStep012345startSAADADEADEBD(B),p(B)2,AD(C),p(C)5,A4,D3,ED(D),p(D)1,AD(E),p(E)2,DD(F),p(F)4,E∞∞∞[email protected] 12Example: Dijkstra’s AlgorithmStep012345startSAADADEADEBADEBCD(B),p(B)2,AD(C),p(C)5,A4,D3,ED(D),p(D)1,AD(E),p(E)2,DD(F),p(F)4,E∞∞∞[email protected] 13Example: Dijkstra’s AlgorithmStep012345startSAADADEADEBADEBCADEBCFD(B),p(B)2,AD(C),p(C)5,A4,D3,ED(D),p(D)1,AD(E),p(E)2,DD(F),p(F)4,E∞∞∞[email protected] 14Dijkstra’s Algorithm:DiscussionAlgorithmcomplexity:nnodes- Eachiteration:needtocheckallnodes,w,notinS- n*(n+1)/2comparisons:O(n**2)- Moreefficientimplementationspossible:O(n*log(n))Oscillationpossible- E.g.,linkcost=amountofcarriedtrafficADCB11+ee0e1100initiallyADCB2+e0001+e1… recomputeroutingADCB02+e1+e100…recomputeADCB2+e0e01+e1…[email protected] 15DistanceVectorRoutingAlgorithmIterative:continuesuntilnonodesexchangeinfoAsynchronous:nodesneednot exchangeinfo/iterateinlockstep!Distributed:eachnodecommunicatesonly withdirectly-attachedneighborsRouting(distance)tabledatastructure– eachroutermaintains- Rowforeachpossibledestination- Columnforeachdirectly-attachedneighbortonode- EntryinrowYandcolumnZofnodeXdistancefromXtoY,viaZasnexthop)},({min),(),( [email protected] 16Example:Distance(Routing)TableAEDCB681212D()ABCDA1764B148911D5542EcosttodestinationviadestinationD(C,D)Ec(E,D)+min{D(C,w)}Dw==2+2=4D(A,D)Ec(E,D)+min{D(A,w)}Dw==2+3=5D(A,B)Ec(E,B)+min{D(A,w)}Bw==8+6=[email protected] 17RoutingTableForwardingTableD()ABCDA1764B148911D5542EcosttodestinationviadestinationABCDA,1D,5D,4D,2Outgoinglinktouse,costdestinationDistance(routing)tableForwarding[email protected] 18DistanceVectorRouting:OverviewEachlocaliterationcausedby:- Locallinkcostchange- Messagefromneighbor:itsleastcostpathchangefromneighborEachnodenotifiesneighborsonlywhenitsleastcostpathtoanydestinationchanges-

View Full Document

Berkeley ELENG 122 - Intra-domain routing

Sign up for free to view:

This document and 3 million+ documents and flashcards
High quality study guides, lecture notes, practice exams
Course Packets handpicked by editors offering a comprehensive review of your courses
Better Grades Guaranteed


School:
Email:
New Password:
Confirm Password:

This preview shows page 1-2 out of 7 pages.

Berkeley ELENG 122 - Intra-domain routing

Sign up for free to view:

Please select your school