Patent ID: 7171490

Claim:
A method for updating a routing trie stored in a routing engine, the routing engine comprised in a router for routing packets in a communications network, the method implemented in the routing engine and comprising the steps of: generating a plurality of writes, each of said writes specifying a location in the routing trie to be modified and a new value to be written into said location in the routing tile when said write is applied, each of said writes having a timestamp associated therewith, said timestamp representative of a time when said write is generated; identifying one or more excess writes and another write, wherein said excess writes are writes which specify a location in said routing trie to be modified but are redundant with respect to the other identified write, said one or more excess writes having associated timestamps representative of times which are not later than the time represented by the timestamp associated with the other identified write, and wherein each difference between the times represented by the timestamp associated with each one of said excess writes and the timestamp associated with said other identified write is less than a given threshold, and wherein applying said other identified write without having applied any of said excess writes results in a routing trie state which is equivalent to a routing trie state which would result from applying any one or more of said excess writes and said other identified write; and updating the routing trie by applying the other identified write and not applying any of the excess writes.