• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:
    Die Erfindung betrifft eine neuartige Suchmaschinenarchitektur, welche sich insbesondere für einen Router für paketorientierte Netzwerke eignet. Durch die geschickte Kombination von ternärem inhaltsadressierbaren Speicher mit konventionellem dynamischem RAM-Speicher unter Ausnutzung der physikalischen Eigenschaften des dynamischen RAM-Speichers ergibt sich die Möglichkeit, auch bei Vorliegen sehr großer Routingtabellen eine schnelle Paketweiterleitung in Hardware sicherzustellen und gleichzeitig mit einer wirtschaftlich vorteilhaften Größe des ternären Speichers auszukommen.
    公开号:DE102004006102A1
    申请号:DE200410006102
    申请日:2004-02-06
    公开日:2005-09-08
    发明作者:Oliver Bartels
    申请人:Oliver Bartels；
    IPC主号:G06F17-30
    专利说明:
    [0001] DerErfindung liegt die Aufgabe zugrunde, einen Router für paketorientierteDatennetzwerke zu bauen, der das Paketrouting auch bei sehr großen Routentabellensehr schnell durchführt,ohne dabei die Grenzen der Wirtschaftlichkeit zu sprengen.
    [0002] BisherigeRouter setzen auf eine baumorientierte Darstellung in einem konventionellenSpeicher wie beispielhaft in EP1155537 oder US5909440 beschrieben oderauf eine geschachtelte Darstellung wie in US6631419 gezeigt. KonventionellerSpeicher ist heutzutage infolge erheblicher Fortschritte der Halbleitertechnologiesehr preiswert mit großerKapazitäterhältlich,die allgemeine Bezeichnung in der Fachwelt hierfür lautet RAM (Random AccessMemory).
    [0003] Diegrößten Kapazitäten bietendabei dynamische Speicher (DRAM), bei denen die Information durcheine Ladung einer Kapazitätrepräsentiertwird und lediglich ein weiterer MOS-Transistor zur Ankopplung andie Speichermatrix benötigtwird. Allerdings haben dynamische Speicher den Nachteil, dass eineschnelle Adressierung nur innerhalb einer bereits selektierten Seiteund Zeile einer Speichermatrix möglichist, da beim Vorgang der Selektierung dieser Seite und Zeile Ladungenaus den Speicherkondensatoren der jeweiligen Zeile in die Leseverstärker transferiertwerden und zuvor die Inhalte der zuvor angewählten Zeile durch einen Rücktransfer wiederhergestellt werden müssen(Precharge). Hingegen kann auf ein oder mehrere Bits aus einer im Leseverstärker gehaltenenZeile durch einen Multiplexer oder Burst Transfer sehr schnell zugegriffen werden.
    [0004] Eineandere Alternative ist der Einsatz statischer RAM Speicher, diesehalten die Information durch rückgekoppelteSpeicherzellen, welche jedenfalls zwei Zustände statisch einnehmen können. Der Zugriffkann hier auf jedes einzelne Speicherelement ohne die Einschränkungendes Ladungstransfers erfolgen, allerdings benötigt jede Speicherzelle erheblichmehr Platz auf dem Halbleiter, da eine Vielzahl von platzverbrauchendenMOS-Transistoren pro Speicherzelle erforderlich ist.
    [0005] Üblich istauch eine Kopplung von dynamischen Speicher mit statischem Speicherdurch sogenannte Cache-Architekturen, dabei werden im Bedarfsfallganze Datenblöckeaus dem dynamischen in den statischen Speicher transferiert, umdort fürerwartete künftigeZugriffe zwecks schnellem Abruf vorgehalten zu werden.
    [0006] Für den Einsatzim Netzwerkrouting hat diese Architektur jedoch den Nachteil, dassbei plötzlich aufkommendemDatenverkehr in unterschiedlichste Richtungen zum Beispiel durchgrassierende Computervirenprogramme (auch als „Schlechtwetterbedingung" in der Fachweltbezeichnet) extrem viele Zugriffe auf unterschiedlichste Adressenstattfinden und somit eine Cache Architektur, unabhängig davon,ob sie sich auf das RAM oder bereits gefundene Routingziele bezieht,ihren Vorteil verliert und dieser sich durch den zusätzlichenVerwaltungsaufwand sogar in einen Nachteil umkehren kann, im Extremfall hatdies schon zu Netzzusammenbrüchengeführt.
    [0007] Einweiterer Ansatz ist der Einsatz von einfachem inhaltsorientiertemSpeicher, abgekürztCAM (Content Adressable Memory), wie er beispielsweise in US6658002 eingesetzt wird.
    [0008] Beiinhaltsadressierbarem Speicher wird typischerweise von statischemRAM ausgegangen und jeder Speicherzelle ein Vergleicher zugeordnet.Wird nun ein Datenwort an den Speicher angelegt, so erkennt eineSpeicherzeile mittels der Vergleicher eine vollständige Übereinstimmungund gibt somit ein Signal beispielsweise an einen Prioritätsencoder,der seinerseits hieraus die Adresse der Zeile codiert. Ein typischerEinsatzbereich ist die Auflösungvon MAC Adressen auf einem lokalen IEEE 802.3 LAN Netzwerk in zugeordneteSwitch Ports oder IP Adressen.
    [0009] Eineweitere Möglichkeitist die Nutzung von ternäreminhaltsadressierbarem Speicher, abgekürzt TCAM. Dieser Speichertypwird üblicherweisenicht in konventionellen Computersystemen eingesetzt, sondern wurdeprimärfür Netzwerkhardwareentwickelt, um eine schnelle Routingentscheidung für bestimmteZiele anhand der IP Adresse zu fällenoder um Filtermaßnahmenanhand der Quell- und Zieladresse zu steuern. Dazu befindet sichals Besonderheit dieses Speichertyps an je zwei Speicherzellen für jeweilsein Bit eine Logikschaltung, die den Inhalt dieser Speicherzellenmit einem angelegten Datenmuster vergleicht. Dabei bestimmt daserste Bit eines Speicherzellenpaars, welches Datenbit erwartet wird, während daszweite Bit festlegt, ob überhauptein Vergleich stattfinden soll, dieses Bit wird daher auch als Maskenbitbezeichnet, da es das Vergleichsergebnis für diese ternäre Speicherzelleim Bedarfsfall maskiert. Alternativ kann auch ein Bit ein Pflicht-Eins-Datum oder alternativkeinen Vergleich selektieren, währenddas andere Bit ein Pflicht-Null-Datum oder keinen Vergleich bestimmt, dieUmsetzung zwischen beiden Darstellungen ergibt sich aus einer einfachenLogiktabelle.
    [0010] Beidem TCAM Speicher besteht nun zusätzlich zu den üblichenSchreib-/Lesevorgängenbei normalem RAM die Möglichkeit,dass an das Speicherfeld ein externes Datenwort zu Vergleichszwecken angelegtwird. Um eine Übereinstimmungfür einDatenwort innerhalb des Speicherfeldes mit dem externen Datenwortfeststellen zu können,müssenalle Logikschaltungen der Speicherzellenpaare eines Datenwortesdieser Feststellung zustimmen (Und-Verknüpfung), entweder in dem einedirekte Übereinstimmungdes jeweiligen Datenbits festgestellt wird oder indem das Maskenbitdes Speicherzellenpaares signalisiert, dass keine Übereinstimmungnotwendig ist. Da es jedenfalls drei sinnvolle Zustände für ein Speicherelementgibt („Gleich-Eins", „Gleich-Null", „Kein-Vergleich-erforderlich") wird dieser Speichertypauch als ternärerinhaltsadressierbarer Speicher bezeichnet, auch wenn z.B. mit „Datenwortgesperrt" ein vierterZustand fürein Speicherzellenpaar denkbar wäre.
    [0011] Soferndurch einen solchen Vergleich ein Datenwort gefunden wird, wirdentweder direkt die Adresse des Datenwortes zurückgegeben oder über diesenAdressindex ein weiterer statischer RAM Speicher adressiert, welcherseinerseits assoziierte Daten zu diesem Wort, z.B. einen Zeigerauf ein Objekt, zurückliefernkann. Im IP Routing Bereich findet sich hier üblicherweise die Adresse desnachfolgenden Routers und die Bezeichnung des Ziel-Interfaces.
    [0012] Nachteiligist dabei jedoch, dass sich trotz Fortschritten in der Halbleitertechnologiebisher nur relativ kleine Speichergrößen in der Region bis maximalein Megaworte realisieren lassen, zudem haben TCAM Speicher einerelativ hohe Verlustleistung. Bereits die heutige globale Routingtabelleläßt sichnur unter erheblichen Einschränkungenoder Kosten in einem solchen Speicher ablegen, weswegen er hauptsächlich für Switchemit nur lokalen Zielen eingesetzt wird.
    [0013] Hingegenstellt die geplante Umstellung des globalen Internet Routings von32 Bit Adressen im Rahmen des IPv4 Protokolls auf 128 Bit Adressenim Rahmen des IPv6 Protokolls ganz neue Anforderungen an die InternetRouter, welche von den heutigen Geräten nur unzureichend erfüllt werdenund daher derzeit eine Einschränkungdes IPv6 auf lediglich provideraggregierbaren Adressraum bedingen,welche dem Ziel einer lebenslangen Zuteilung eines Adressraums aneine Person, Organisation oder an ein Gerät völlig zuwiderlaufen und damitden kommerziellen Erfolg des neuen IPv6 sehr in Frage stellen.
    [0014] Einbesonderes Problem ist dabei die Mischung sehr großer miteiner Vielzahl kleiner Adressbereiche, hierdurch kommt es bei einerbaumorientierten Suche zu großenBaumtiefen und langen Suchzeiten, gleichzeitig verbietet die Größe der Routingtabellebei weitem eine komplette Ablage in einem TCAM Speicher schon alleineaus wirtschaftlichen Gründen.
    [0015] DasProblem wird erfindungsgemäß durch diein Patentanspruch 1. beschriebene Einrichtung gelöst, derenFunktion im folgenden anhand eines Ausführungsbeispiels erläutert wird: Dieeinzelnen Routingziele werden durch Tabelleneinträge repräsentiert,welche einerseits den zu routenden Bereich beschreiben und andererseitsdie Weiterleitungsinformationen wie die Adresse des nächsten Routers(Next Hop), das abgehende Interface und gegebenenfalls weitere Filter-und Bearbeitungsregeln beinhalten. Weiterhin möglich ist auch die Codierungder Datenquelle, um mehrere getrennte Routingtabellen beispielsweisefür virtuelleRouter kombinieren zu können.
    [0016] MehrereTabelleneinträgewerden nun mittels eines geeigneten Algorithmus kombiniert, hierfür bietensich insbesondere Clusteralgorithmen oder in einer vorteilhaftenAusführungder Erfindung gemäß Unteranspruch12 auch Algorithmen mit definierten Teilungskriterien ähnlich einemB-Baum an.
    [0017] Nachder Gruppierung der Tabelleneinträge werden nun zusammengehörende Einträge in einer Zeileeines dynamischen RAM Speichers abgelegt und der dieser DRAM Zeilezugeordnete Eintrag im TCAM Speicher so gesetzt, dass nur alle demCluster gemeinsamen Bits der Zieladresse im TCAM als gültig gekennzeichnetwerden, hingegen alle Bits, welche Unterscheidungen aufweisen, ausmaskiertwerden.
    [0018] Dadas TCAM typischerweise entsprechend der Reihenfolge der Einträge einePrioritätvergibt, kann gemäß Unteranspruch11 auch ein hierarchisch geteilter Adressbereich gut abgebildetwerden. So könnenbeispielsweise mehrere Ziele mit kleinen Adressbereichen in einerDRAM Zeile untergebracht werden, welcher seinerseits in dem Fall,dass keiner dieser Bereiche getroffen wird, mittels Defaulteintrag aufden übergeordnetengrößeren Adressbereich verweist.Dieser würdeauch direkt durch seinen niedriger priorisierten Eintrag im TCAMgefunden, falls die Adresse nicht innerhalb des Clusters der kleinenZiele liegt und somit gleich dieser niedriger priorisierte, abereinen größeren Adressbereichabdeckende Eintrag mit der ihm zugeordneten DRAM Zeile zum Tragenkommt.
    [0019] Dieeigentliche Wahrnehmung dieser hier beschriebenen Verwaltungsaufgabenerfolgt sinnvollerweise durch eine auf einem Steuerrechner ablaufendeSoftware, die Verwaltungsaufgaben sind im Gegensatz zum eigentlichenProzess der Paketweiterleitung gewöhnlich nicht zeitkritisch.
    [0020] Indem im folgenden beschriebenen Ausführungsbeispiel der Erfindungwird genau deren Anwendung zur schnellen Ermittlung von Paket-Weiterleitungsinformationengezeigt, die einzelnen Zieladressbereichen für die Zieladressen der Datenpaketezugeordnet sind.
    [0021] Wiein Bild 1 gezeigt erfolgt beim Eintreffen der Zieladresse die Abfragedes TCAM Speichers (TC1), dieser wird im Fall, dass die Adresseim Adressbereich eines bekannten Routingeintrags liegt, einen Indexausgeben. Dieser kann nun gemäß Unteranspruch2. mittels direkter Kopplung mit dem dynamischen DRAM Speicher oderdem zugeordneten Controller des Speichers, im letzteren Fall typischerweisebestehend aus Multiplexern und Registern im Adresspfad zum DRAM,zur Adressierung einer Zeile des DRAM Speichers verwendet werden.
    [0022] Eineweitere Möglichkeitist die vorherige Umrechnung des Index zu einer Adresse mittelseines Rechenwerks gemäß Unteranspruch3., um beispielsweise einen Offset zur Mehrfachnutzung des DRAMauch fürandere Speicherzwecke zu schaffen oder unterschiedliche Tabellenverschiedener virtueller Router zu adressieren.
    [0023] Gemäß einerbesonders vorteilhaften Ausführungder Erfindung entsprechend Unteranspruch 4. findet ein weiteres,insbesondere statisches RAM zur Festlegung der Adresszuordnung (Mapping)Verwendung, hierdurch brauchen bei dynamischen Änderungen der Routingtabelleentsprechend neu eintreffender Routen über dynamische Protokolle keine Datenblöcke im dynamischenRAM verschoben werden, es reicht hierzu aus, bei Verschiebungeninfolge Prioritätsänderungenim TCAM die Abbildung der Indexwerte auf die DRAM Seiten und Zeilenim weiteren statischen RAM zu ändern.Sinnvollerweise wird man bei der Belegung des TCAM Speichers zunächst Zwischenräume durchkomplett ungültige Suchwortefreihalten, um auch hier eine Verschiebung ganzer Bereiche zunächst zuvermeiden. Sollte dies jedoch nicht mehr möglich sein, so wird gemäß Unteranspruch4 zumindest eine Datenverschiebung im DRAM weitgehend vermieden.Diese Variante wurde in Bild 1 mit dem Mapping-RAM (MR1) gewählt.
    [0024] Nachdemdie Seiten- und Zeilenadresse am dynamischen RAM (DR1) vorliegt,kann nun diesem Speicher der Befehl zum Lesen der selektierten Zeile gegebenwerden. Der Vorgang wird erfindungsgemäß durch eine Steuerlogik (CL1)eingeleitet, welche bei Vorliegen des Index und nach durchgeführter Adressumsetzungtätig wird.Für dennun folgenden Suchvorgang innerhalb der Zeile kann diese entwederoffengehalten werden oder es wird der gesamte Zeileninhalt mittelseines Burst Modus in ein Zwischenregister oder Zwischenspeichertransferiert und sogleich der Precharge zur Vorbereitung des nächsten Zugriffsausgelöst.
    [0025] Hierzeigt sich der besondere Vorteil der Erfindung: Durch die eindeutigeZuordnung eines Clusters von Einträgen auf eine Zeile des DRAMSpeichers werden weitere zeitaufwendige Zugriffe vermieden, trotzdemkann preisgünstigerDRAM Speicher zum Halten einer extrem großen Tabelle verwendet werden.Die langsame Zeilenzugriffsgeschwindigkeit des DRAM ist somit entschärft.
    [0026] Nachdemsich der Zeileninhalt nun im schnellen Zugriff befindet, kann innerhalbdieser Zeile die Suche nach der Zieladresse fortgesetzt werden.Im in Bild 1 gezeigten Beispiel macht dies eine Suchmaschine (SE1),diese stellt auch die Weiterleitungsdaten für das Paket bereit. Genausoist jedoch der Einsatz der Haupt-CPU des Routers denkbar. Dieseist zumeist ohnehin zur Pflege der Datenbestände in den verschiedenen Speicherbaugruppen erforderlich.Gemäß Unteranspruch5. sind die Routingziele als Bereiche abgelegt, wobei für die weitere Sucheprinzipiell nur eine Bereichsgrenze oder ein Trennwert benötigt wird.
    [0027] Eineweitere Möglichkeitist die unmittelbare Ablage der Startadresse eines Zieladressblocksund der Größe diesesBlocks, wobei insbesondere die Codierung der Anzahl der gültigen Adressbitsin der gängigenIP-Prefix-Notation gemäß Unteranspruch 6.sinnvoll ist.
    [0028] Besondersvorteilhaft ist letztere Codierung in Zusammenspiel mit einem parallelenVergleicher gemäß Unteranspruch9. Eine besonders hohe Suchgeschwindigkeit ergibt ein unmittelbarauf dem DRAM integriertes paralleles ternäres Register, welches über die – entsprechendder Anzahl der in der Zeile gespeicherten Adresseinträge wiederholtaneinandergereihte – gesuchteAdresse, gegebenenfalls zuzüglichmittels Maskierung übersprungenerDatenfelder, abgefragt wird. ÜberPrioritätsencoderkann der übereinstimmendeBereich ermittelt werden, hieraus folgt unmittelbar der gesuchteEintrag.
    [0029] Jedochläßt sichauch mit marktüblichen Standard-Speicherbausteineneine schnelle Suche innerhalb der selektierten DRAM Zeile durchführen, einvorteilhafter Weg ist mit der sortierten Ablage und einer Binärsuche inUnteranspruch 7. beschrieben.
    [0030] Besonderseinfach gestaltet sich eine Suche in Hardware, wenn gemäß Unteranspruch8. beispielsweise immer zwei Bits der relativen Adresse des Eintragsin der DRAM Zeile ersetzt werden.
    [0031] EinBeispiel soll dies verdeutlichen: Gegeben sei eine relative binäre Startadresse1000. Sollte der erste Vergleich eine Übereinstimmung ergeben, soist die Suche beendet. Bei einem gesuchten Datenwort, welches kleinerist als der Eintrag an der Startadresse, werden die obersten beidenBits durch das Muster 01 ersetzt, somit ergibt sich 0100 als nächste Adressefür einenzu testenden Eintrag. Bei einem größeren Datenwort werden hingegendie obersten beiden Bits durch das Muster 11 ersetzt, somit entsteht1100 als nächsteTestadresse. Im ersteren Fall kann wieder unter 0100 direkt einTreffer erzielt werden, oder es wird, jetzt um ein Bit nach rechts geschoben,die Adresse durch Ersetzung nach dem gleichen Schema, jetzt aberfür daszweit und drittwertigste Bit, zu 0010 bei kleinerem Suchwort oder 0110manipuliert. Im zweiten Fall wird, so kein direkter Treffer erzieltwurde, auf 1010 bei kleinerem Suchwort oder auf 1110 weitergesucht.In diesem Fall ginge es ohne Treffer bei 1101 oder 1111 weiter,danach ist die Suche abgeschlossen.
    [0032] Dierelative Adresse 0000 wird bei diesem Verfahren nie erreicht, esliegt auf der Hand, diese zum Abspeichern des Default Eintragesgemäß Unteranspruch11 zu verwenden.
    [0033] Eineandere Möglichkeitist die Verwendung einer Hash-Funktion gemäß Unteranspruch 13. Im einfachstenFall eines linearen Hashes bietet sich hier an, mittels Barrel-Shifterdas erste Bit, welches infolge Maskierung nicht mehr durch den TCAMEintrag eindeutig bestimmt ist, als oberstes Bit der zeilenrelativenAdresse zu verwenden, die auf dieses Bit folgenden Bits werden entsprechendmit verschoben. Hierdurch kann beispielsweise der TCAM Eintrag einen/20 IP Prefix abdecken, der Hash Key könnte dann bei beispielsweise64 Einträgenpro DRAM Zeile jeweils ein /26 Netz codieren, wobei hingegen ein /25Netz auf zwei /26 Einträgeverteilt würde.
    [0034] Eineweitere Möglichkeitist die Kombination eines Burst Transfers gemäß Unteranspruch 14. mit einersequentiellen Suche gemäß Unteranspruch 15.,wobei sich dieses Verfahren nur bei kleineren DRAM Zeilenlängen undschnellen DRAM'sanbietet, da ansonsten die sequentielle Suche zuviel Zeit in Anspruchnimmt.
    [0035] Selbstverständlich kanndie hier beschriebene Zieladresse auch weitere Daten codiert enthalten, beispielsweiseInformationen überdie Auswahl einer aus mehreren bereitstehenden Routingtabellen oder über einenProtokolltyp, eine gewünschteServiceklasse oder Dienstleistungsqualität oder Datenwegbandbreite.
    [0036] Generelleignet sich die Erfindung nicht nur zur Ermittlung von Zielen vonDatenpaketen, naheliegend ist zunächst die Mitbenutzung einersolchen Einrichtung in einem Router zur Realisierung von Filterlistenfür bestimmteQuell- und Zieladressen oder Protokolle, hier ist auch eine gestaffeltemehrfache Suche in der ausgewähltenDRAM Zeile möglich.
    [0037] Desweiteren ist die Anwendung als Datenbankprozessor denkbar, oderauch die Verwendung als Zusatzeinheit einer Zentraleinheit (CPU)eines Rechners zur Unterstützungder Garbage Collection, wie im folgenden Beispiel beschrieben: Eswird ein konventioneller Rechner eingesetzt, mit einem speziellenBefehl zum Speichern von Zeigern auf Datenblöcke. Hierbei signalisiert dieHaupt-CPU bei einem Schreibvorgang eines Zeigers in den konventionellenSpeicher übereine Leitung die Zeigereigenschaft, die Zusatzeinheit kann sodanndie Zieladresse des Zeigers in einem freien Eintrag einer DRAM Zeileder Erfindung ablegen, welcher durch die Kombination aus Zieladresseund Zeigeradresse definiert wird. Wird nun der Zeiger verändert, sokann dieser schnell durch vorheriges Lesen der alten Zieladresseund Rekombination mit der Zeigeradresse zum Suchwort wieder ausgetragenwerden. Im Fall der Untersuchung eines Speicherblocks im Rahmen derGarbage Collection kann jetzt die Basisadresse dieses Blocks alsmittels Maske auf lediglich die Zieladresse verkürztes Suchwort genutzt werden,die Erfindung stellt dann eine Auflistung der betroffenen Zeigerbereit, welche bei einer Verschiebung dieses Blocks zu korrigierensind. Bei einem Nullergebnis der Suche wird der Block nicht mehrreferenziert und kann freigegeben werden.
    权利要求:
    Claims (15)
    [1] Datenverarbeitungseinrichtung zur schnellen Suchevon Datenworten in einer Datenbasis, insbesondere zur Suche vonNetzwerk-Adressbereichen anhand einer gegebenen Adresse, hier wiederumbevorzugt zur schnellen Ermittlung der Weiterleitungsinformationeneines Datenpaketes in einem Router oder Switch in einem Datennetzwerkanhand der Zieladresse des Datenpaketes, dadurch gekennzeichnet,dass (1) das zu findende Datenwort, insbesondere die Zieladresse,zunächstan mindestens einen ternären inhaltsadressierbarenSpeicher (im folgenden TCAM genannt) zur Abfrage angelegt wird,das TCAM ordnet durch parallelen Vergleich des angelegten Datenwortesmit seinem Inhalt dem Datenwort mindestens einen Index eines übereinstimmendenInhaltsdatenwortes des TCAM zu, wobei der Vergleich infolge der Ternäreigenschaftdes Speichers auf ausgewählte Bitspro Inhaltsdatenwort beschränktwird und wobei im Fall keines derart teilweise übereinstimmenden Inhaltsdatenwortesdieser Suchvorgang beendet wird, (2) der so vom TCAM ermittelteund ausgegebene Index übermindestens eine Adresszuordnung mindestens einer Seiten- oder Zeilenadresseeines dynamischen RAM Speichers (im folgenden auch bei synchronendynamischen Speicher allgemein DRAM genannt) zugeordnet wird, (3)mindestens eine so adressierte Seite oder Zeile des DRAM nach Bereitstellungdes Index und nach Ausführungder Adresszuordnung durch eine Steuerlogik, insbesondere eine mitder erfolgreichen Bereitstellung des Index gestartete Ablaufsteuerung,selektiert und zum Lesen – insbesonderedurch Ladungstransfer in die Leseverstärker oder Zeilenregister – geöffnet wird, (4)in den so bereitgestellten Daten der Seite oder Zeile eine weiterekonventionelle Suche nach mindestens einem zu dem Datenwort passendenEintrag durchgeführtwird. Der Zugriff auf diese Daten kann dabei entweder direkt oder über mindestenseine Zwischenlogik oder übermindestens ein Zwischenregister oder über mindestens einen Cache-Speicher erfolgen.
    [2] Einrichtung nach Anspruch 1., dadurch gekennzeichnet,dass die Zuordnung zu (2) eine lineare Zuordnung des Index zur Seiten-oder Zeilenadresse ist, welche durch direkte Zuordnung der Index-Signalleitungenzu den Adressleitungen des dynamischen RAM Speichers hergestelltwird.
    [3] Einrichtung nach Anspruch 1., dadurch gekennzeichnet,dass die Zuordnung zu (2) durch mindestens eine arithmetische Recheneinheitaus dem Index mittels vorgegebener Rechenvorschrift vorgenommenwird.
    [4] Einrichtung nach Anspruch 1., dadurch gekennzeichnet,dass die Zuordnung zu (2) mittels mindestens eines weiteren Zuordnungsspeichers,insbesondere statischen RAM Speichers, dadurch hergestellt wird,dass der Index als Adresse an den Zurdnungsspeicher angelegt wirdund das so adressierte Datenwort in diesem Zuordnungsspeicher dieSeiten- oder Zeilenadresse des DRAM beinhaltet.
    [5] Einrichtung nach Anspruch 1., dadurch gekennzeichnet,dass die Einträgezu (4) in der Seite oder Zeile des DRAM Bereichsgrenzen, insbesondereOber- oder Untergrenzen sind oder zur Trennung von zwei Bereichengeeignete Zwischenwerte (Teilungswerte) sind.
    [6] Einrichtung nach Anspruch 1., dadurch gekennzeichnet,dass die Einträgezu (4) in der Seite oder Zeile des DRAM Adressprefixe bestehendaus Basisadresse und Prefixlänge – letztereinsbesondere codiert als Anzahl der gültigen Adressbits – sind, wobeidie Prefixlängeindirekt die Größe des Adressbereichsdes jeweiligen Eintrags überderen dualen Logarithmus codiert. Alternativ kann die Prefixlänge auchals Bitmaske, welche die adressrelevanten Bits codiert, abgelegtsein.
    [7] Einrichtung nach Anspruch 1., dadurch gekennzeichnet,dass die zugeordneten Einträgezu (4) in der Seite oder Zeile des DRAM sortiert abgelegt sind unddie konventionelle Suche eine Binärsuche oder eine Baumsucheist.
    [8] Einrichtung nach Anspruch 1. oder 6. oder 7., dadurchgekennzeichnet, dass die zugeordneten Einträge zu (3) in der jeweiligenSeite oder Zeile des DRAM dergestalt abgelegt sind, dass diese imRahmen einer binärenSuche durch iterative Bildung der seiten- oder zeilenrelativen (Spalten-)Adresse gefunden werden können.Hierzu wird ausgehend von einer Startadresse schrittweise jeweilseine bitweise Adressveränderung,insbesondere an benachbarten Bitpaaren ausgehend vom höchstwertigenAdressbit, dergestalt durchgeführt,dass zunächstein Vergleich des gesuchten Datenwortes mit dem zu diesem Zeitpunktadressierten Eintrag vorgenommen wird und, sofern nicht unmittelbareine Übereinstimmungfestgestellt wird, abhängigvom Vergleichsergebnis eine Ersetzung an der zu dieser IterationgehörendenErsetzungsstelle im Adresswort gemäß einer festgelegten Ersetzungsregelvorgenommen wird und daraufhin der nächste Iterationsschritt gestartetwird.
    [9] Einrichtung nach Anspruch 1., dadurch gekennzeichnet,dass zur schnelleren Suche des zu findenden Datenwortes nach demZugriff auf die Seiten- oder Zeilenadresse des DRAM parallel mehrereInhalte der so adressierten Seite oder Zeile des DRAM in eine paralleleVergleichseinheit geleitet werden.
    [10] Einrichtung nach Anspruch 9., dadurch gekennzeichnet,dass es sich bei der Vergleichseinheit wiederum um ein ternäres Registeroder um einen weiteren Ternärspeicherhandelt, dieser kann auch in Form eines Cache Speichers auf demDRAM Chip selbst integriert sein.
    [11] Einrichtung nach Anspruch 1. oder 5. oder 6. oder7. oder 8., dadurch gekennzeichnet, dass für mindestens eine Seite oderZeile des DRAM ein weiterer (Default-) Eintrag besteht, welcherim Rahmen der Suche dann ausgewähltwird, falls diese keinen passenderen Eintrag in dieser Zeile findet,insbesondere um eine hierarchische Schachtelung von Adressprefixenauf die Datenbasis effizient abzubilden.
    [12] Einrichtung nach Anspruch 1., dadurch gekennzeichnet,dass zum Aufbau der Inhaltsdatenworte des TCAM mindestens ein definiertesTeilungskriterium und im Fall dynamischer Änderungen des Datenbankinhaltsmindestens ein Zusammenfassungskriterium verwendet wird, welchesbei Überlaufeiner Seite oder Zeile des DRAM infolge weiterer geforderter Einträge die Verteilungauf weitere Seiten oder Zeilen des DRAM eindeutig festlegt und lediglichdie allen Einträgeneiner Seite gemeinsamen Bits als gültige Bits in den entsprechendenTCAM Inhaltsdatenworten unmaskiert läßt. Im Fall dynamischer Änderungenstellt das Zusammenfassungskriterium sicher, dass bei Unterbelegungeiner Seite oder Zeile diese gegebenenfalls mit ihren logischenNachbarn zusammengelegt wird.
    [13] Einrichtung nach Anspruch 1. oder 5. oder 6., dadurchgekennzeichnet, dass jedem Indexwert des TCAM oder jeder Seiten-oder Zeilenadresse des DRAM ein weiteres Datenwort, welches insbesonderedie Startposition des ersten maskierten Bits des jeweiligen TCAMInhaltsdatenwortes codiert, zur Bildung eines Hash-Schlüssels zugeordnetwird, welcher insbesondere durch Bitverschiebung des Suchdatenwortesmit einer aus der Startposition abgeleiteten Verschiebungsdistanzgewonnen werden kann. Anhand dieses Hash-Schlüssels kann dann in der selektiertenSeite oder Zeile des DRAM mindestens ein mit hoher Wahrscheinlichkeitunmittelbar passender Eintrag zum Vergleich herangezogen werden.
    [14] Einrichtung nach Anspruch 1., dadurch gekennzeichnet,dass zur Durchführungder Suche ein Burst-Transfer der Seiten- oder Zeilendaten aus dem DRAMvorgenommen wird.
    [15] Einrichtung nach Anspruch 14. und 5. oder 14. und6., dadurch gekennzeichnet, dass die Daten im Rahmen des Burst-Transfersunmittelbar einem Vergleicher nacheinander übergeben werden, welcher anhandder Bereichsgrenzen oder anhand der zu einer Maske expandiertenPrefixlängenangabe, welchedie Differenz aus der Basisadresse des Adressprefix und der gesuchtenAdresse maskiert, oder anhand unmittelbar in der Seite oder Zeileabgelegter Maskendaten einen passenden Adressprefix als Ergebnisder Suche ermittelt. Die Differenz wird hierbei insbesondere durcheine Exklusiv-Oder Operation gebildet.
    类似技术:
    公开号 | 公开日 | 专利标题
    US9871728B2|2018-01-16|Exact match hash lookup databases in network switch devices
    US9627063B2|2017-04-18|Ternary content addressable memory utilizing common masks and hash lookups
    US20170364606A1|2017-12-21|Table lookup apparatus using content-addressable memory based device and related table lookup method thereof
    US8880554B2|2014-11-04|Method and apparatus for high performance, updatable, and deterministic hash table for network equipment
    US7440304B1|2008-10-21|Multiple string searching using ternary content addressable memory
    US6389507B1|2002-05-14|Memory device search system and method
    JP4565793B2|2010-10-20|Method and apparatus for longest match address lookup
    US6522632B1|2003-02-18|Apparatus and method for efficient prefix search
    US6717946B1|2004-04-06|Methods and apparatus for mapping ranges of values into unique values of particular use for range matching operations using an associative memory
    US8112578B2|2012-02-07|Low power, hash-content addressable memory architecture
    US7610271B2|2009-10-27|Method and apparatus for performing a binary search on an expanded tree
    EP2040184B1|2019-03-13|Datenbank und Datenbankverarbeitungsverfahren
    US6430190B1|2002-08-06|Method and apparatus for message routing, including a content addressable memory
    US7058642B2|2006-06-06|Method and data structure for a low memory overhead database
    JP4614946B2|2011-01-19|限定サイズを有する限定数のサブデータベースに分割された転送データベースを効率的にサーチするシステムと方法
    US5909440A|1999-06-01|High speed variable length best match look-up in a switching device
    US7254748B1|2007-08-07|Error correcting content addressable memory
    US6661787B1|2003-12-09|Integrated data table in a network
    DE602004010922T2|2008-12-18|Speicher und stromeffizienter mechanismus für schnelles tabellennachschlagen
    US6775281B1|2004-08-10|Method and apparatus for a four-way hash table
    US6711041B2|2004-03-23|Content addressable memory with configurable class-based storage partition
    US6917934B2|2005-07-12|Search engine for large database search using hash pointers
    EP1486040B1|2006-08-02|Vlan tabellenverwaltungssystem in hardwarebasierten paketvermittlungsstellen für speichereffizientes auslesen und einschreiben
    US6963868B2|2005-11-08|Multi-bit Patricia trees
    US7277426B2|2007-10-02|Method and apparatus for reordering entries in a multi probe lookup
    同族专利:
    公开号 | 公开日
    DE102004006102B4|2005-12-08|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    法律状态:
    2005-09-08| OP8| Request for examination as to paragraph 44 patent law|
    2006-06-01| 8364| No opposition during term of opposition|
    2013-12-12| R119| Application deemed withdrawn, or ip right lapsed, due to non-payment of renewal fee|Effective date: 20130903 |
    优先权:
    申请号 | 申请日 | 专利标题
    DE200410006102|DE102004006102B4|2004-02-06|2004-02-06|Datenverarbeitungseinrichtung zur schnellen Suche von Datenworten|DE200410006102| DE102004006102B4|2004-02-06|2004-02-06|Datenverarbeitungseinrichtung zur schnellen Suche von Datenworten|
    [返回顶部]