Två versioner av Internet (IP) router-table problem beaktas. I den första, router tabellen består av n par tuples av formuläret (p, a), där p är en adress prefix och a är nästa-hop information. I denna version av router-table problem, ska vi utföra följande åtgärder: infoga en ny tuple, ta bort en befintlig tuple, och hitta tuple med längst matchning-prefix för en given destination adress. Vi visar att var och en av dessa tre operationer kan utföras i O(log n) tid i värsta fall med hjälp av ett prioritetssök träd. I den andra versionen av router-table problem som beaktas av oss, varje tuple i tabellen har formen (r, a), där r är en rad måladresser matchas av tuple. Den uppsättning tuples i bordet är konfliktfri. För denna version av router-table problemet utvecklar vi en datastruktur som använder prioritetssökning träd samt röd-svarta träd. Denna datastruktur tillåter oss att utföra var och en av åtgärderna infoga, ta bort, och hitta tuple med mest specifika matchning-intervall för en given måladress i O(log n) tid var i värsta fall. Infoga och ta bort åtgärder bevara konfliktfri egendom av uppsättningen tuples. Experimentella resultat presenteras också.
Lu och Sahni Ref föreslår också en datastruktur med prioriterade sökträd och rödsvarta träd för representation av regeltabeller där filtren är konfliktfria.
o(log n) dynamic router-tables for prefixes and ranges
{'venue': 'IEEE Transactions on Computers', 'journal': None, 'mag_field_of_study': ['Computer Science']}