Automatic IP Address Assignment on Network Topologies

1 2006 02 February11,2006 AbstractWe considertheproblemofautomatingtheassignm entofIPaddressestonodesina assignmentexploitsthenaturalhierarchy inthenetworkandassignsad-dressesinsucha ,wherescaleprecludesmanualassignment,lar geroutingtablescanlimitnetworksize,andre alismcanmatter. It benefitsenterprisenetworks,wherelargerou tingtablescanoverburdenthelegacy thendescribeseveralofthealgorithmicdirec tionsandmetricswehave explored, presenta comparative assessmentofoural-gorithmsona bestalgorithms,yieldingthehighestquality namings,canassignaddressestonetworksof50 00routers,comparabletotoday s largestsingle-ownernetworks, a ,a ,eachofthennodesina net-workwouldneedtostorea routingtableentryforalln , (CIDR),theroutingschemeusedintheInternet today.

2 InCIDR,a ,names,intheformofIPad-dresses,have alreadybeenassignedtohosts,soonceroutesa recomputed,minimizingthesizeofa , inseveralotherimpor-tantsettings, Address eshave ,forexample, vir-tualIPaddressspacetonametheirmembers ,andthereareincreasinglymoreenablingtech nologies[34,28] andrea-sons[2] , ,oneoftheauthors institutionsrecentlycompleteda projecttore-assignaddressestotheirentire 20,000+ enterprisesusememory-constrainedlegacy routers[29], , , a good addressassignmentisonethatreflectstheund erlyinghierarchy ,withmorespecificprefixesoverridingmoreg eneralones,anaddressassign-mentthatexplo itsthehierarchy ,andthusthecompu-tationalchallengesofide ntifyinga inferringhierarchy inthispracticalsetting topology, ,suchascompactnessofagraph,andthedegreet owhichverticesareequivalent,fromthepersp ective ofrouting, ,butstemsfroma problemformulationthatcapturesthecomplex itiesandnu-ancesofassigningIPaddressesto networkinterfacesinanenvironmentwhereCID R aggregationis [5]

3 Typicallyemphasizecertaindetailsofnetwor kmod-eling,suchastopologyandqueuing, , many useanabstractnotionofnodeiden-tity, ,workontopologygenerationhasconcentrated onproducingrepresentative Topologies ,butnotonrepresen-tative ,suchasGT-ITM[13] andBRITE[26], ,inturn,discouragesnew particulartopologygenerator, weinsteadaimtoprovidegeneralalgorithmsth atcanassignIPaddressesto any router-leveltopology, , networkemulationenvironmentssuchasEmu-la b[39]andModelnet[36]have becomepopular. emulatetopologiessimilartotheonesusedbys imulators;infact, runrealIPstacks,ratherthansim-ulationsof stacks,IPaddressesarea ,addressassignmentistypicallydonemanuall yorinanadhocmanner. ,suchasrandomassignment,mayproduceconsis tentaddresses,butthey re-quirementforaccurateexperimentalevalu ationinareassuchasdynamicroutingalgorith ms,firewalldesignandplace-ment, morebasiclevel,mostsimulatorsarefundamen tallyunrealisticinthatthey ,asrelatedworkhasfound[35, 7].

4 Addressassignmentsinrealnetworksareinflu encedbythehierarchy presentinthetopologyofthenetwork, is notcleartowhatextentpolicy canbemodeled,giventhatis otherwork[1] ,weconcentrateonthehierarchicalpropertie sofnetworks,attemptingtoassignaddressest hat,byminimizingroutingtablesizes,matcht henaturalhierar-chy We buildupona theoreticalformulationofinterval rout-ingtoformulatetheIPaddressassignmen tproblem,andbelieve wehelptoopenthisgeneralareaofstudy. Wedeviseageneralmetric, RoutingEquivalenceSets, thatquantifiestheextenttowhichroutestose tsofdestinationscanbeaggregated. We developthreeclassesofalgorithmstooptimiz eIPnaming,eachwitha fundamentallydifferentapproachtotheprobl em. We devisea pre-processingstepthatimprovestherun-nin gtimesofseveralofouralgorithmsbyordersof magnitudewithoutsacrificingsolutionquali ty.

5 We findtwo ofthem,recur-sive partitioningandtournamentRES,to beparticularlyeffective andefficientenoughtorunontopologiesaslar geastoday s largestsingle-ownernetworks[3],inafew secondsanda minute, cleantheoreticalversionoftheproblem, detailsthealgorithmswehave devel-oped,whileSection4 ,wediscussrelatedwork, globaladdressassignmentau-tomatically, ,anassignmentinwhichIPaddressesareassign edtoeachnetworkinterfaceina tominimizetheto-talspaceconsumptionofrou tingtables,whichinturnhelpsto minimizepacket processingtimeat ,IPaddressassignmentdirectlyimpactsthesi zesofroutingta-bles,sincea setofdestinationswithcontiguousIPaddress esthatsharethesamefirsthopcanbecaptureda sa singlerout-ingtableentry. It is alsoessentialtonamehostsfroma com-pactnamespace, detail,it is ,anotherpossi-bleconsiderationis thatofproducinga namingschemethatyieldsrouteswithsmallstr etch, ,routesusedareat worsta , widelyusedintheoreti-calstudies, ,considerthenetworkdepictedinFigure1,inw hichnodesareassignedaddressesfromf1; : : : ;7g.

6 IntervalroutingtableentriesareshowninFig ure2 fortheoutboundinterfacesofnodes1,2, canexpressitsshortest-pathrouteswithtwo disjointintervals,oneperinterface,whichc orrespondstoa ,node1mustusea , ,theroutingtableatnode7 electedtogroupnode3 onthesameinterfaceasnodes1, 2, and4 tosave two formaldefinitionofintervalrouting,consid erann-nodeundirectedgraphG= (V; E), wherewewillrefertoverticesashosts,andane dge(u; v)asa pairofinterfaces(oneatvertexuandoneatver texv).Anaddressassign-2 Figure1 3H1H1 4G4 6A3F5 6D7H4 5I6F7 GFigure2:Selectedinterval routingtablesfromtheabove inVa uniquelabelfromthenamespaceofintegersf1; : : : ng. Theroutingtableofvertexuassociateseachla belofeveryvertex withoneedge(u; v)(thenext hop).Inthismanner, a subsetoflabelsinAis nodeusingintervalrouting,thesizeofthemin imalsetofintervalsis theroutingtablesize, denotethenumberofentriesintheroutingtabl eofvertexubyku.

7 Thetheoryliteraturehascon-sideredquestio nssuchasdeterminingtheminimumvalueofkfor whichanassignmentresultsinroutingtablesa llofsizesmallerthank[37, 18, 15]. Fora givengraph,thisvalueofkis arepri-marilyconcernedwiththeaveragerout ingtablesize,soweworkwiththefollowingobj ective function:Objective:Fora graphG, is wellknownthatsearchanddecisionproblemsof thisformareNP-complete,andseveralheurist icsandapproxi-mationalgorithmsareknown[1 8]. Ourfocusis ontheprac-ticalconsiderationsthatcauseCI DR routingtobea signif-icantlydifferentproblemthaninterv alrouting; describedsofarandtheactualaddressingprob lemthatmustbesolvedin ,althoughintervalroutingis intuitivelyappealingandelegant,routingta bleag-gregationinpracticeis performedusingthesetofclasslessinter-dom ainrouting(CIDR)rules[17],addingsignific antcomplexity.

8 Second,inIPaddressing,eachindividualinte r-face(outboundedge)ofa nodeis assignedanaddress(label),noteachvertex, , widelyusedlocal-areanetworktechnologiess uchasEthernetprovideall-to-allconnectivi ty, andthesenetworksarebestdescribedbyhyperg raphs[6](describedbelow), CIDR addressis anaggregatethatisspecifiedasa CIDR addresscanexpressonlythosein-tervalsofIP addressesthatarea poweroftwo insizeandthatstartonanaddressthatis a [c 2y;(c+ 1) 2y)forintegerscandy. Thismorerestric-tive aggregationschememeansthatanIPassignment mustbecarefullyalignedinordertofullytake ,dealingwiththisalignmentchallengeconsum esmany bitsofthenamespace,andaddressspaceexhaus tionbecomesanissueevenwhenthenumberofin- terfacesis aspectofourwork, , ,thein-tervalsdelimitedbyCIDR routingtableentriesmayoverlap,butthelong est(andconsequentlymostspecific)matching interval is advantageousforCIDR,asit admitsmoreflexibilitythanbasicinterval ,they areassignedtonet-workinterfaces, adistinctionwithouta difference,butforhostswithmultipleinterf aces,suchasnetworkrouters, , singleAS(AutonomousSys-tem)]

9 Usingshortest-pathrouting,whena packet is sentto anyoneofa host s addresses,it is typicallyexpectedtotake theshortestpathtoany ,it is valuabletobeabletoaggregatealladdressesa ssignedtoa , butalsowithhowtheinterfacesona simulationandemulationen-vironmentsarebe strepresentedashypergraphs, sincetheyoftencontainlocal-areanetworkss uchasEthernet,whichenableall-pairsconnec tivityamonga setofnodesratherthanconnectivitybetweena ,sinceit isa generalizedgraphinwhicheachedgeisassocia tedwitha setofverticesratherthana ,whenassigningaddressestoa hy-pergraph, ,thisbecomesmoredif-ficulttoreasonabout, sinceeachnetworkedgemaybeasso-ciatedwith a ,weworkinsteadwiththedualhyper-graph[6]( seeFigure4);tofindthedualhypergraphofagi ventopology, wecreatea hypergraphwithverticesthatcorrespondtoli nksintheoriginaltopology, andhyperedgesthatcorrespondto hostsin theoriginaltopology.

10 Eachvertexinthedualhypergraphis ,byla-belingverticesofthedualhypergraph, wearelabelingthenetworkLANsandlinksinthe originaltopology. We labeltheverticeswithIPsubnets, nowdescribeourmethodsforproducinga labelingthatstrivestogenerateCIDR routingtablesofminimumaveragesize, :Sincetherunningtimesofouralgorithmsis dependentuponthesizeofthegraph, :We thenembedtheverticesofthegraphintothelea vesofa binarytrie,whereeachin-ternalnodereprese ntsa thelinchpinofourapproach, :To minimizetheimpactofad-dressspaceexhausti on,wedevisea constitutethemaintechni-calcontributions ofthispaper. We describethesealgorithmsinthissection,and theninSection4, stepofTrieEmbeddinghave superlineartimecomplexityin thesizeofthegraph, achieve scalingwehave deviseda prepassphaseFigure3 goals.