US8559434B2 - Packet forwarding in a network - Google Patents

Packet forwarding in a network Download PDF

Info

Publication number
US8559434B2
US8559434B2 US13/059,958 US200813059958A US8559434B2 US 8559434 B2 US8559434 B2 US 8559434B2 US 200813059958 A US200813059958 A US 200813059958A US 8559434 B2 US8559434 B2 US 8559434B2
Authority
US
United States
Prior art keywords
link
representations
node
packet
representation
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Fee Related, expires
Application number
US13/059,958
Other languages
English (en)
Other versions
US20110149973A1 (en
Inventor
Christian Esteve Rothenberg
Petri Jokela
Jimmy Kjällman
Pekka Nikander
Teemu Rinta-Aho
Jukka Ylitalo
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Telefonaktiebolaget LM Ericsson AB
Original Assignee
Telefonaktiebolaget LM Ericsson AB
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Telefonaktiebolaget LM Ericsson AB filed Critical Telefonaktiebolaget LM Ericsson AB
Assigned to TELEFONAKTIEBOLAGET LM ERICSSON (PUBL) reassignment TELEFONAKTIEBOLAGET LM ERICSSON (PUBL) ASSIGNMENT OF ASSIGNORS INTEREST (SEE DOCUMENT FOR DETAILS). Assignors: ESTEVE, CHRISTIAN, JOKELA, PETRI, KJALLMAN, JIMMY, NIKANDER, PEKKA, YLITALO, JUKKA, RINTA-AHO, TEEMU
Publication of US20110149973A1 publication Critical patent/US20110149973A1/en
Application granted granted Critical
Publication of US8559434B2 publication Critical patent/US8559434B2/en
Expired - Fee Related legal-status Critical Current
Adjusted expiration legal-status Critical

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/16—Multipoint routing
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/34—Source routing
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/56—Routing software
    • H04L45/566—Routing instructions carried by the data packet, e.g. active networks
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/74—Address processing for routing
    • H04L45/745—Address table lookup; Address filtering
    • H04L45/7452—Multiple parallel or consecutive lookup operations
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/74—Address processing for routing
    • H04L45/745—Address table lookup; Address filtering
    • H04L45/7453—Address table lookup; Address filtering using hashing
    • H04L45/7459—Address table lookup; Address filtering using hashing using Bloom filters

Definitions

  • Publish-Subscribe (“pubsub”) oriented networking, as described by Mikko sherelä, Teemu Rinta-Aho, and Sasu Tarkoma in “RTFM: Publish/Subscribe Internetworking Architecture”, published in the proceedings of ICT Mobile Summit, Swiss, Jun. 11-13, 2008, focuses on data, as opposed to the original Internet Protocol which focuses on hosts and end points, as primary named entities. This focus on naming end points, and universal connectivity between end points, creates a number of well known problems. Firstly, the current inter-networking paradigm allows parties to communicate with each other in an open network even though some parties are outright malicious, and others selfish. Secondly, a major fraction of contemporary applications are more in the business of information dissemination than that of end-to-end, two-way communication.
  • broadcasting or multicasting is a more natural basic operation than sending a message to a single, explicitly identified recipient.
  • Multicasting is the delivery of information to a group of specified destinations simultaneously, whereas “broadcasting” refers to transmitting information such that it may in principle be received by any device on a network.
  • inter-networking based on the publish-subscribe paradigm would be more natural, efficient, and easy-to-implement than the current sender-oriented one.
  • One idea behind the Publish-Subscribe paradigm is that one can avoid unwanted data delivery from one node to another.
  • a sender can deliver a data packet to a host identified with an IP address without any explicit request from the receiver. This causes many problems, as it results in a user receiving unwanted, and even possibly malicious, data.
  • This problem could be overcome by abandoning receiver-based addressing, such as used in the IP address scheme, as this removes the possibility of sending data to a destination host without the destination host having requested the data.
  • the IP address scheme were abandoned it would be necessary to provide a new mechanism that can be used to route packets through the network.
  • the routing information may define one or more paths from the source node to the destination node(s), or it may define respective paths from the source node to two or more different destination node(s). When part of the paths are overlapping, such overlapping information is encoded only once, thereby representing a delivery tree instead of a set of paths.
  • the routing information may be encoded at a source node of the network.
  • the routing information may be encoded at a routing server with the encoded routing information being forwarded to the source node.
  • the method may comprise determining a path from the source node to the destination node(s) by interrogating the routing information contained in the header of the packet.
  • the method may comprise generating d candidate compact representations of set membership from d representations of the identifiers (d is an integer greater than 1).
  • One of the compact representations of set membership may then be selected for use.
  • the selection may be made according to a user-determined criterion such as, for example which representation has the lowest rate of generating false positives, which representation has the lowest rate of generating false positives for a sub-set of one or more of the identifiers, or which representation will not generate false positives for a sub-set of one or more of the identifiers.
  • the selected compact representation of set membership may for example be included in a packet header to provide routing information.
  • the routing information may comprise a plurality of link identifiers, each identifying a respective network link or node. Alternatively, it may comprise an identifier or identifiers that each identify a partial path containing two or more network links.
  • the routing information may comprise one of a plurality of candidate representations of the one or more identifiers.
  • the routing may comprise selecting, from a plurality of look-up tables, a look-up table corresponding to the received representation of the one or more identifiers.
  • a third aspect of the invention provides a network node comprising means for receiving a packet. It further has means for interrogating routing information contained in the header of the packet as a compact representation of set membership to determine one or more links along which the packet is to be sent from the node and/or one or more other nodes to which the packet is to be sent from the node. The node forwards the packet along the determined link(s) and/or to the determined other node(s).
  • the routing information may comprise a plurality of link or node identifiers, each identifying a respective network link or node. Alternatively, it may comprise an identifier or identifiers that each identify a full or partial path containing two or more network links.
  • the network node may be adapted to select, from d look-up tables each corresponding to one of d candidate representations of the one or more identifiers, a look-up table corresponding to the received representation of the one or more identifiers.
  • the compact representation of set membership may be a Bloom filter.
  • the method of the first aspect may comprise defining a path through a network, which path comprises a plurality of segments, each segment having an associated identifier. An identifier, different from the identifiers associated with each segment included in the path, is assigned to the path. Encoding the routing information comprises encoding the identifier assigned to the path, rather than encoding the identifiers associated with each segment of the path.
  • the identifier assigned to the path may be unrelated to the identifiers associated with each segment included in the path.
  • At least one segment of the path may comprise two or more links each of which directly connects two network nodes.
  • a fourth aspect of the present invention provides a network node for providing packet routing information, the node being adapted to encode routing information from a source node to one or more destination nodes into a compact representation of set membership for inclusion into a header of a packet that is to be sent from the source node to the destination node(s).
  • the network node may be adapted to send the compact representation of set membership to the source node, for example if the network node is a routing function node.
  • the network node may be the source node, in which case the network node may be adapted to include the compact representation of set membership into a header of a packet that is to be sent from the source node.
  • the compact representation of set membership may be a Bloom filter.
  • the network node may be adapted to encode routing information comprising representations of one or more identifiers by generating d representations of at least some of the identifiers; generating d candidate compact representations of set membership from the d representations of the identifiers; and selecting one of the candidate compact representations of set membership.
  • the network node may be adapted to encode routing information comprising representations of one or more identifiers by generating d representations of at least some of the identifiers; generating d candidate compact representations of set membership from the d representations of the identifiers; and sending two or more of the candidate compact representations of set membership to another node.
  • the other node may for example be the source node, which is then able to select one of the received candidate compact representations and include the selected compact representation in a packet header.
  • the other node may select one of the received candidate compact representations but, rather than itself making use of the selected compact representation, may forward the selected compact representation to another node.
  • Each identifier may identify a respective network link, a respective node, or a full or partial path containing two or more network links.
  • a fifth aspect of the present invention provides a method of generating, a compact representation of a set of identifiers.
  • the method comprises initially generating d representations of the identifiers, and d candidate compact representations of set membership are generated from the d representations of the identifiers.
  • One of the candidate compact representations of set membership is then selected for use.
  • the selection may be made on the basis of a criterion pre-defined by a user.
  • the method may be implemented by a suitable processor, for example in a processor contained in or constituting a network node.
  • the representations of the identifiers may be compact representations.
  • a “compact” representation of an identifier is meant a representation that has fewer bits set to one, preferably substantially fewer bits, than the identifier that it represents.
  • Use of a compact representation has the advantage that few, if any, limits are placed on the length and format of the identifier itself.
  • the compact representation of set membership may be a Bloom filter.
  • aspects of the invention provide a computer-readable article containing instructions which, when executed on a processor cause the processor to perform a method of the first aspect of the invention or to perform a method of the second aspect of the invention.
  • the invention also provides a network node for encoding packet routing information comprising representations of one or more identifiers by: generating d representations of at least some of the identifiers and generating d candidate compact representations of set membership from the d representations of the identifiers.
  • the invention also provides a network node for providing packet routing information comprising representations of one or more identifiers, the node being adapted to receive a plurality of candidate compact representations of set membership and to select one of the compact representations of set membership according to a pre-determined criterion.
  • the criterion which may be user-defined, may for example which representation has the lowest rate of generating false positives, which representation has the lowest rate of generating false positives for a sub-set of one or more of the identifiers, or which representation will not generate false positives for a sub-set of one or more of the identifiers.
  • the invention also provides a source node adapted to receive a compact representation of set membership, and to include the compact representation of set membership in a packet header to provide routing information.
  • the compact representation of set membership may be a Bloom filter.
  • FIG. 1 is a schematic diagram illustrating the process of adding items to a Bloom Filter
  • FIG. 2 is a schematic diagram illustrating the process of verifying whether a data item has been added to a Bloom Filter
  • FIG. 3 is a schematic diagram illustrating a Bloom Filter verification returning a false positive
  • FIG. 4 illustrates forwarding a packet through a network according to an embodiment of the invention
  • FIG. 5 illustrates forwarding a packet through a network according to an embodiment of the invention
  • FIG. 6 illustrates creating a virtual link through a network according to another embodiment of the invention.
  • FIG. 7 is a schematic diagram of a Virtual Link Setup packet
  • FIG. 8 illustrates another method of creating a virtual link through a network
  • FIG. 9 illustrates virtual links that create Multicast trees
  • FIG. 10 illustrates multiple paths through a network for a single packet
  • FIG. 12 is a block flow diagram illustrating provision of forwarding information in a packet header
  • FIG. 13 is a block flow diagram illustrating forwarding a packet through a network according to the embodiment of FIG. 5 ;
  • FIG. 14 illustrates generation of tags corresponding to an identifier
  • FIG. 15 schematically illustrates a forwarding node according too another aspect of the invention.
  • FIG. 16 is a schematic illustration of a packet header
  • FIG. 17 illustrates a method according to another embodiment of the invention.
  • FIG. 18 illustrates the reduction in false positive rate obtainable by an embodiment of the invention
  • FIG. 19 illustrates the false positive rate
  • FIG. 20 is a block flow diagram of a method of another aspect of the invention.
  • the present invention will be described with reference to embodiments in which the routing information is contained in a Bloom Filter.
  • the invention is not limited to a Bloom Filter, and other compact representations comprising encoding routing information into a set membership that can be interrogated to identify a routing information similar to using a Bloom Filter in functionality may be used such as, for example, the representation described by A Pagh et al. in “An Optimal Bloom Filter Replacement”, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pages 823-829 (2005).
  • the invention may also be effected with modified Bloom filters such as disclosed by, for example, M. Mitzenmacher in “Compressed Bloom Filters”, IEEE/ACM Transactions on Networking, Vol. 10, No. 5, p604 (2002).
  • the present invention provides a new Bloom Filter (BF)-based source routing scheme where routing information is included in a BF in the packet header.
  • source routing is used when the source node controls the full path that the packet will take from the source node to the destination node.
  • Other used terms are “strict source routing” when the exact path is known and “loose source routing” when the source node defines only some points in the network through which the packet will travel.
  • Bloom Filters provide an efficient way of including data items in a compact representation of set membership. Few distinct hash values are calculated over a data and these hash values represent certain bits in the Bloom Filter bit string, which during item addition are set to one.
  • link information in the set representation, where link information corresponds to a link between two nodes in the network. From the Bloom Filter where data items have been added, it is impossible to extract the added information. It is only possible to verify if the item is included there or not. There is a small possibility for false positives (informing that the data item has been added, while in fact it has not been added), but no possibility for false negatives.
  • a BF that is used for packet forwarding can create additional packet multiplications in the network due to false positives, which in pub/sub networks is considered to be not harmful as long as there is a way to control the false positive rate. In case of BFs it means that it is possible to control the number of items to be added, and the size of the filter. But, which is more important, the data is always routed at least via links which have been added to the set representation.
  • the BF (e.g. 128 bits long) can be added to a packet header, and it contains the whole route from the source node to the destination node. This may be end-to-end, or only a part of the path between the original data publisher and the subscriber.
  • a network node only a minimal amount of forwarding information needs to be maintained.
  • each node typically maintains a routing table, each table entry holding information needed to identify those packets that will be sent over a given link. In that case, it is possible that the node needs only one entry in the forwarding table for each node that it connects to.
  • the forwarding process is efficient, while the packet identifying information in the forwarding table entry is bitwise ANDed (where “ANDed” denotes the logical AND operation) with the BF in the packet header, and if the result is equal to the packet identifying information, the packet is forwarded to the corresponding outgoing link. If the result is not equal, the identifier for the particular link was never added to the Bloom Filter and the packet is not forwarded to that link.
  • the invention can thus provide compact source routing information in a packet header based on Bloom Filters. This minimises the state information that must be held in network nodes.
  • the identifiers may have free format, in which case their Bloom filter representation is computed in the usual manner of taking k different hashes over the identifier.
  • the link names may be constructed directly of k “1” bits and m-k “0” bits, or k-z . . . , k ⁇ 1, k, k+1 . . . k+z “1” bits and corresponding number of “0” bits, where z is very small, in which case such hashing is not needed in order to construct the Bloom filter.
  • the naming scheme must encode enough of entropy (randomness) to the names in order to avoid hash collisions.
  • link IDs in this invention.
  • a Bloom Filter is a simple way to add data elements in a compact representation of a set, called a filter, and later test if the element has been earlier added to it.
  • a BF is a bit string, containing a pre-defined number of bits, e.g. 128 bits, that are initially all set to zeros.
  • the size of the BF may vary depending on the use. As an example, in FIG. 1 the number of bits in the BF is eight. In a general case, an 8-bit BF would be a very small BF and would, in practice, be unusable for any purpose.
  • Adding a data item to a BF is a process where a number of distinct hash values are calculated from an identifier. In case of the example in FIG.
  • three distinct hash values are calculated by applying three different hashing algorithms to the identifier “data 1 ”, such that each of these values is between 1 and 8. Each of these values represent one bit in the BF. After the hash values are calculated, each corresponding bit in the BF is set to one. In the example of FIG. 1 the three hash values are 3, 6 and 1, and the 1 st , 3 rd and 6 th bits in the Bloom filter are set to “1”. This comprises the link ID for the identifier “data 1 ”.
  • FIG. 1 shows also adding another identifier—“data 2 ”—to the BF.
  • the distinct hash values are calculated similarly, and if the corresponding bit is already set to one in the BF, the bit remains as one.
  • the three hash values obtained from “data 2 ” are 4, 7 and 1, and the 4 th and 7 th in the Bloom filter are set to “1” (the 1 st bit has already been set to “1”, when “data 1 ” was added to the Bloom filter. It is clear that when items are added in this way, there is no possibility to remove any items from the BF; one cannot know if a bit with value “1” comes from one or more data items.
  • FIG. 2 shows the process of checking whether “data 1 ” is a member of the Bloom filter created in FIG. 1 .
  • the three hash values are created for “data 1 ”, using the same three hash algorithms as used to create the Bloom filter, and these are 3, 6 and 1.
  • the Bloom filter is checked, it is found that the 3 rd , 6 th and 1 st bits of the Bloom filter are all set to “1”, and this indicates (correctly) that “data 1 ” is included in the Bloom filter.
  • One feature of a Bloom filter is that process of verifying whether an item is a member of a Bloom filter is not wholly accurate and can give rise to a “false positive”. However, it cannot give rise to a “false negative”. If the data item has indeed been included, the filter verification returns always “true” as the corresponding bits of the Bloom filter will all be “1” (as the calculation process is the same during adding an item to the Bloom filter and during verification). Thus, we get a correct answer. However, if any of the bits checked in the verification process is found to be zero, the verification returns “false” and we know that the item has not been added to the Bloom filter.
  • the rate of false positives depends on the length of the filter and the number of items added to the filter.
  • each link of a network i.e. connection between two nodes, is considered as a identifiable data item having an identifier (or “name”).
  • identifier or “name”.
  • the invention proposes that, when a packet is requested, a path is chosen through a network from a source node to a destination node, which may be described as a sequence of link identifiers.
  • the sequence of link identifiers is encoded into a BF, and the BF is put in the packet header.
  • each packet may carry a lifetime indicator and the identity of a few recently visited nodes, or each node may remember a sufficient number of recently seen packets.
  • a node in the network can determine which outgoing link(s) from the node it should forward the packet along, by interrogating the Bloom filter in the packet header to determine which outgoing link IDs have been added to the Bloom filter in the packet header—if a particular outgoing link identifier has been added to the Bloom filter in the packet header, the packet is forwarded along that link. This process is repeated at each node along the path. (If the path is defined in terms of nodes along the path rather than in terms of the links that make up the path, the node would interrogate the Bloom filter in the packet header to determine to which other network nodes it should send the packet, and the packet is forwarded to the node(s) obtained by interrogating the Bloom filter.)
  • the invention makes use of the advantage of the BF in the sense that it is a compact representation of the data items and that it always returns a correct answer if the data item has been added to the filter.
  • “pub/sub” routing false positives are not a concern, as long as the probability is low. False positives cause the packet to be delivered to a wrong destination—which is not considered to be harmful, as long as the rate of false positives can be controlled.
  • the rate of false positives depends on the length of the BF, the number of bits representing a data item and the number of data items that have been added to the filter.
  • FIG. 4 is a schematic view of a simple network having nodes R 1 to R 5 .
  • a packet source 1 is connected to node R 1 and a packet destination (or “sink”) 2 is connected to node R 3 .
  • Each link between two of the nodes R 1 to R 5 is provided with a link identifier; in the embodiment of FIG. 4 direct Bloom-filter compatible link IDs are used and they are generated as a directed identifiers so that each link has two separate link IDs, one for each direction. This is needed to avoid loops in some situations (described below).
  • the link from node R 1 to node R 2 has link ID 001001001
  • the reverse link from node R 2 to node R 1 has link ID 110001000.
  • the link IDs in the example are chosen to be very short, 9 bits, for illustration but will in practice be longer than this.
  • the embodiment of FIG. 4 relates to a Pub/Sub network in which the functionality required for locating and delivering data between source and destination nodes can be considered to consist of three different operations; Rendezvous, Routing, and Forwarding.
  • the Rendezvous mechanism is responsible for maintaining publication location information in the network
  • the Routing mechanism is responsible for creating and configuring routes from the data location to the subscribing node based on the information that is maintained in the rendezvous system
  • the Forwarding function is responsible for forwarding the actual data packets through the network.
  • the source 1 publishes publication P.
  • This information is stored in the Rendezvous system 3 so that the publication P maps to its current location.
  • the location information for the publication P can be found from the Rendezvous system 3 (step 2 of FIG. 11 ). This provides information about the current location of the data and the destination where it needs to be delivered.
  • the Routing function 4 needs the source and destination node information for building a forwarding path between the source 1 and the destination (the sink 2 ).
  • the Routing function 4 maintains information about network links, the associated link Ids, and the nodes which the link connects—for example, the information maintained in the Routing function can be the node pairs and, for each node pair, the link ID of the link between them. Once the information about link IDs, and the nodes that the links connect, is in the Routing layer, it can build a path through the network using the source and destination node information.
  • the Routing function has knowledge about the network topology.
  • Routing function gets a request to build a path between nodes A and B, it can create the path using the links from e.g. A to C and C to B, if A and C as well as B and C are directly connected.
  • the Routing function 4 when the Routing function 4 is notified that the sink 2 has requested the publication P from source 1 , it can create, based on the source and destination node information, a path from the source 1 to the destination 2 (step 3 of FIG. 11 ).
  • the routing system uses the network topology information and determines that the data needs to travel the path R 1 -R 2 -R 3 .
  • the determined path may be expressed as a sequence of link identifiers, in this case as ⁇ 001001001, 001011000 ⁇ to denote a path formed of the link R 1 to R 2 and the link
  • link IDs There are various ways to determine the link IDs. They can be automatically generated by the nodes (for example a node can assign a link ID for its own outgoing links towards nodes that it know it is connected directly to) and communicated afterwards to the routing function, or they can be assigned by other instances and configured on the nodes.
  • a link ID may for example be obtained by applying a required number of hashing algorithms to an underlying identifier and obtaining a bit mask from the resultant hash values.
  • a suitable bit mask may be obtained by setting k bits of a string of bits of length m bits to be “1” with the remaining bits remaining as “0” (where the Bloom filter has a length of m bits and k ⁇ m).
  • all link IDs In practice it is advantageous for all link IDs to have the same bit mask length m, since it would be inefficient to process variable length fields in hardware. Hence, in practice it is advantageous to determine the maximum affordable size for m, and then use that as the bit mask length for all link IDs.
  • the number k of bits set to “1” in the bit mask forming a link ID may vary in the network, and the number k of bits set to “1” does not have to be the same for all links.
  • the link ID for a high capacity link may be formed by setting k 0 ⁇ 1 bits of a string of bits of length m bits to be “1” whereas a normal capacity link has a link ID formed by setting k 0 bits of a string of bits of length m bits to be “1”. This may increase the number of false positives on the high capacity link, but should reduce the number of false positives on other links.
  • the link ID for a low capacity link may be formed by setting k 0 +1 bits, or even k 0 +2 bits, of a string of bits of length m bits to be “1”. This should reduce the number of false positives on that link, but may increase the number of false positives on other links.
  • the k bits that are set to “1” to form a link ID may be selected at random. However, the k bits may be selected in other ways—for example, locally it might make sense to select the k bits for each outgoing link from node so that there is no overlap between the link IDs of the links from a node. Consequently, the probability of sending a packet over more than one link from a node when it should be send over just one outgoing link will drop drastically (although more false positives may occur elsewhere).
  • the Routing function 4 creates (step 5 of FIG. 11 ) a BF containing the link IDs of the path.
  • the link IDs are constructed as describe above and contain “m” bits of which k (or k ⁇ 1, k+1, etc) ones are “1” bits
  • each link ID is ORed into the BF (where ORed denotes the logical OR operation), so that the BF contains information about each of the links on the path.
  • the path contains two links, from R 1 to R 2 (link ID: 001001001) and from R 2 to R 3 (link ID: 001011000), and the generated Bloom filter is therefore 001011001.
  • the routing function sends (step 6 of FIG. 11 ) the created source routing BF to the data source 1 together with the publication P identifier.
  • the source node creates a packet from the publication P and puts the received BF into the header (step 7 of FIG. 11 ).
  • the packet is now ready for delivery, and may be sent by the data source 1 (step 8 of FIG. 11 ).
  • routing information may be encoded in the Bloom filter at the source node rather than at the routing function 4 as described above.
  • the packet which contains routing information as a Bloom filter in its header (in the example of FIG. 5 the Bloom filter in the packet is the Bloom filter 001011001 generated in FIG. 4 ) is first sent to R 1 .
  • R 1 interrogates the routing information in the packet header by checking the Bloom filter included in the packet header (step 2 of FIG. 12 ), and tries to match (step 3 of FIG. 12 ) the link ID values of the outgoing links from R 1 to the BF in the packet header.
  • each forwarding table entry in R 1 may consist of the link ID of an outgoing link and the index of the corresponding physical link.
  • the matching process is as illustrated in FIG. 2 .
  • the BF in the packet header further matches the link towards R 3 (step 4 ) and the packet is forwarded to node R 3 using that link.
  • the final delivery from node R 3 to Sink 2 may be handled in any convenient way, and the invention is not limited to any particular method of final delivery.
  • the link ID towards the Sink 2 could be added to the BF when the BF is created, and the packet may be forwarded from node R 3 to the sink in a similar way as it is forwarded between the nodes R 1 , R 2 and R 3 .
  • R 3 could maintain the subscription information from the sink, matches the publication ID on the subscription and forwards the data to the sink.
  • the link ID of the virtual link is encoded, for example in a Bloom filter, and is put into the packet header.
  • the forwarding tables of the nodes along the virtual link are configured to include the link ID of the virtual link and the appropriate forwarding destination(s).
  • a node receives a packet having the link ID of the virtual link in its header, it forwards the packet to the destination(s) associated in its forwarding table with the link ID of the virtual link.
  • the routing function when the routing function is delivering data from R 1 to R 3 . For some reason, this partial path is heavily loaded and multiple different transmissions use the same path. It may therefore pay to define a “Virtual link” between R 1 and R 3 .
  • the routing function has defined such a virtual link from R 1 to R 3 via R 2 , and has given it a virtual link ID.
  • the virtual link is defined from two single links R 1 -R 2 and R 2 -R 3 , but a virtual link may include more that two single links. The new virtual link is thus R 1 -R 2 -R 3 .
  • a generated virtual link has a link ID, which need not be directly related to the link IDs of the underlying links used to create the virtual link.
  • the virtual link R 1 -R 2 -R 3 is given the link ID 101000100.
  • the link ID of the virtual link may be an m bits long bitmask of which k bits are “1” and k-m bits are “0”, as described for the link IDs, or it may be obtained by applying a hash function to an underlying identifier for the link.
  • the link ID is a bitmask
  • a new virtual link When a new virtual link is set up it has to be communicated to the nodes that belong to the newly created virtual link.
  • One way to communicate information about the virtual link is to deliver the new virtual link ID to each of the nodes of the link separately but it may alternatively be possible to use a more elegant way and allow the nodes to get this information from a separate control packet delivered through the relevant nodes.
  • the routing function may use a Virtual Link Setup Packet (ViLS), see FIG. 7 , to inform nodes about the new virtual link ID.
  • ViLS Virtual Link Setup Packet
  • the BF in the ViLS packet header contains a normally calculated BF, to which both R 1 -R 2 and R 2 -R 3 link IDs have been added as described above so that the packet is forwarded along the link R 1 -R 2 -R 3 .
  • the new virtual link ID is included, as well as the lifetime of the virtual link if this is needed.
  • Each node that receives the ViLS packet can read the link ID from the ViLS packet, and add the link ID to its forwarding table with the corresponding outgoing link.
  • the publication ID field or some other field in the packet header may be used to indicate the ViLS packet type, but there are also other methods for this. There is no need to include other information in the data field of the ViLS packet related to setting up forwarding table entries in nodes—the BF in the packet header may be used for this purpose, thus the outgoing links defined in the node's forwarding table are the same as where the BF in the packet would route the packet from the node and where the ViLS packet is next sent to.
  • a ViLS packet may explicitly encode the link IDs of the links forming the virtual link, for example, in the data part of the packet.
  • the link IDs are explicitly encoded into a ViLS packet, each node along the virtual link will set up the forwarding table for the virtual link by comparing the outgoing link IDs with the explicitly encoded link IDs in the packet, disregarding the BF in the packet header for this purpose.
  • the Routing function injects the newly built ViLS to node R 1 .
  • the node R 1 notices that this is a control packet, obtains the required information for the new forwarding table entry describing the new virtual link from the packet data field and puts the new entry into its forwarding table.
  • the destinations for this entry may be determined by the BF in the ViLS packet header or by explicitly listing them, as described above.
  • the same destinations are added to the forwarding table as where the ViLS packet will be further delivered by the normal packet forwarding mechanism.
  • node R 1 adds the link ID of the virtual link R 1 -R 2 -R 3 to its forwarding table, against the outgoing link to node R 2 .
  • the ViLS packet is then forwarded to node R 2 , where the process is repeated—so that node R′′ adds the link ID of the virtual link R 1 -R 2 -R 3 to its forwarding table, against the outgoing link to node R 3 .
  • the ViLS packet is then forward to the next node, and so.
  • FIG. 6 a virtual link is built using real links. It is also possible to define a new virtual links by combining existing virtual links. FIG. 8 shows how this is done.
  • a virtual link R 1 -R 2 -R 3 -R 4 -R 5 is defined such that one segment is the virtual link R 1 -R 2 -R 3 and another segment is the virtual link R 3 -R 4 -R 5 .
  • a virtual link may alternatively be defined such that at least one segment is an actual link and at least one segment is a virtual link.
  • a virtual link defined in this way is given a link ID that is different from (and need not be related to) the identifiers of its constituent segments, and from the identifiers of the actual links included in the virtual link.
  • the virtual link R 1 -R 2 -R 3 -R 4 -R 5 of FIG. 8 is given a link ID that need not be related to the link IDs of the two constituent Virtual links R 1 -R 2 -R 3 and R 3 -R 4 -R 5 nor to the link IDs of the underlying network links R 1 -R 2 , R 2 -R 3 , R 3 -R 4 , R 4 -R 5 .
  • the link ID of the virtual link R 1 -R 2 -R 3 -R 4 -R 5 may be added to the forwarding tables of the nodes R 1 -R 2 -R 3 -R 4 using a ViLS packet as described above.
  • the operation is similar to that described for FIG. 6 , with the link IDs included in the BF being the IDs of the virtual link R 1 -R 2 -R 3 and the virtual link R 3 -R 4 -R 5 .
  • a virtual link may have an unlimited lifetime, or it may have a limited lifetime. As indicated in FIG. 7 , the ViLS packet may contain also this lifetime information, if it is known. In such a case, nodes purge the virtual link from their forwarding table after its lifetime expires.
  • the above description of the invention relates to a packet being sent from a source to a single destination node.
  • the invention is not however limited to this, and may be used to deliver a packet from a source to two or more different destination nodes. This may be done by adding link IDs that define paths to two or more destinations to the Bloom filter to be included in the packet header.
  • virtual links relate to a packet being sent from a source to a single destination node
  • creating multi-path or multicast virtual links is also possible. This may be done by adding to a BF two or more link IDs that both define links out from one node. This is shown in FIG. 9 , where a virtual link including R 1 -R 2 -R 3 , R 1 -R 4 -R 5 and R 1 -R 4 -R 6 is defined (with link ID 001001001)
  • the full multicast tree can be implemented by ORing Links R 1 -R 2 , R 2 -R 3 , R 1 -R 4 , R 4 -R 5 and R 4 -R 6 into the same BF.
  • FIG. 9 sets up a virtual multicast tree using exactly the same method.
  • each node that will send the data to more than one destination determines this in the forwarding table by associating a virtual link ID to multiple destination links (so that the forwarding table of node R 4 , as an example, lists both the link to node R 5 and the link to node R 6 against the link ID (001001001) of the virtual link).
  • the details of the virtual link may again be distributed using a ViLS packet.
  • the routing function creates a virtual link ID (001001001) for the tree, generates a ViLS packet and injects it into R 1 .
  • a virtual multicast tree is setup in the network.
  • BF 001001001
  • FIG. 9 shows the forwarding tables for R 2 and R 4 .
  • Another way to take advantage of multiple paths is to use it for redundancy. It is possible to create paths that have same source and final destination(s), but with multiple parallel paths ( FIG. 10 ). While all paths are unidirectional, we can easily create such multi-path routes (or virtual links) between two nodes.
  • the routes through a network are determined in the routing layer, using single links between nodes or virtual links built from single links between nodes.
  • the invention is not however limited to this.
  • nodes in the network that divide the network into more than a single stateless routing area.
  • These proxy nodes maintain state information between different BFs and publications, and perform label switching between BF headers when packets are passing by.
  • These proxy nodes can be used to avoid filling up Bloom filters or just to divide the network into different administrative domains.
  • one feature of a Bloom filter is that it may give a false positive (that is, advising that an item is present in the filter, while in fact it is not present) when checking for the presence of a link identifier in the BF.
  • a false positive results in packets being forwarded over one or more links which were not included during the construction of the BF. Under the pub/sub paradigm this effect is not considered harmful as long as there is a way to control the false positive rate from becoming too large.
  • the false positive rate depends on the number of items n inserted in the filter, the size of the filter m and the number of bits k that represent an item in the filter (where link identifiers take the form of an m-bit vector with k bits set to 1 and the remaining m-k bits set to 0).
  • a problem with BFs is that they get “full” relatively quickly.
  • the probability of false positives increases as more elements are added to one filter.
  • the number of links that can be represented by the BF is limited when it is desired not to exceed a certain false positive rate.
  • the false positive rate (%) of the BF makes inserting more than 32 link IDs in the BF almost impractical, as this would give a high false positive rate (approx. 3%).
  • 32 link IDs would be not enough for routing purposes (depending on network topology and the number of nodes communicating over the paths defined by the 32 links).
  • the current generation of BFs lacks a mechanism that allows finer control over the effects of false positives given a certain network topology and distribution of link IDs.
  • the Routing function in the envisioned system it would be useful for the Routing function in the envisioned system to have the flexibility of creating routing BFs that are equivalent in their main objective of defining a certain path in the network but that could avoid false positives over certain regions identified by link IDs where false positives are considered more harmful in any terms specified by the network operator.
  • Mechanisms are preferably required to deal with potential malicious source nodes that could generate by themselves a forwarding BF for potential Denial of Service attacks or bypass the intrinsic security of having a forwarding system based on naming links within a topology rather than host identities.
  • a further aspect of this invention addresses the issue of reducing the false positive rate of the BF-based routing approach and provides new mechanisms to control the effects of BFs along the routing paths.
  • a plurality of candidate Bloom filters (or other compact representations of sets, as this aspect also is not limited to Bloom Filters) are generated, and one of the candidate Bloom filters (or other compact representations of sets) is selected based on a pre-determined criterion such as, for example, which of the candidates has the lowest probability of returning a false positive etc. This aspect is based on the choice available during the probabilistic process of generating the BF containing the link identifiers.
  • each link of a network has an associated link identifier (LID or Link ID).
  • LID link identifier
  • the LIDs are used to generate the Bloom filter, so that only one BF is generated for a particular network use.
  • the further aspect of the invention generates two or more candidate BFs that equally” represent the path(s) of a certain network.
  • One way in which this may be done is to generate a plurality of link identifier tags (LITs) associated with each link identifier (LID) and generate a plurality of candidate Bloom filters from the LITs.
  • LITs link identifier tags
  • an optimal set of LITs to be inserted in the BF is selected so that the probability of false positives can be minimized.
  • a plurality of representations (or “tags”) is generated for each identifier.
  • a plurality of candidate Bloom Filters (or a plurality of other compact representations of set membership) are generated from the plurality of representations of the identifiers, and one of the Bloom Filters (or other compact representation of set membership) is selected from the candidates.
  • each LID we compute d compact representations of the LID, where d is an integer greater than 1.
  • Each compact representation is known as a link identifier tag (LIT).
  • LIT link identifier tag
  • d candidate BFs Of the d candidate BFs, one is chosen to be inserted in the packet header to provide routing information, as in the embodiments described above.
  • the primary criterion for choosing the BF to be used can be determined by the user and, for example, may be minimizing the false positive rate—in which case the BF with the largest amount of zeros is selected from the candidate BFs.
  • Other criteria to select the BF can be applied, for instance minimizing the false positive rate for a subset of one or more of the links (or, in general terms, minimizing the false positive rate for a subset of one or more of the identifiers)—this may be of use in for example avoiding certain link identifiers causing false positives that result in packets being forwarded to a certain network region (i.e., to provide the ability to confine false positives in certain network areas).
  • the packet header now includes, in addition to the BF containing the forwarding information, the binary representation of the index d that identifies the set of LITs that were used to construct the BF.
  • the routing nodes receiving the BF of this aspect (referred to as a “d-enhanced BF”) can select the forwarding table appropriate for the set of LITs that were used to construct the BF.
  • the proposed d-enhanced BF approach enables thereby finer control over the effects of false positives that could be applied to enforce routing policies, and can be augmented to provide security features when using BFs as forwarding headers.
  • Embodiments will be described with reference to a Pub/Sub network with three operational layers: Rendezvous, Routing, and Forwarding. Together they provide the functionality required for locating and delivering data between the source and destination nodes.
  • Each link of the network has an associated identifier (Link ID).
  • Link ID identifier
  • d (d>1) representations of each Link ID are generated, and d candidate BFs are generated from the d representations of the link IDs.
  • d candidate BFs are generated from the d representations of the link IDs.
  • Having a set of d representations associated with a link identifier enables more efficient and powerful forwarding schemes by providing finer control over false positives.
  • the power of choice of the LIT-based BFs enables the enforcement of policies for security or inter-zone routing purposes by considering these policies as BF selection and optimization criteria.
  • Link IDs are generated as directed identifier for links of a network. (It will be assumed for simplicity of description that all “links” are actual links between two network nodes, but a link ID may also be the identifier of a “virtual link” as described with reference to FIG. 6 .)
  • a Link ID can take any name form to identify a link between two network elements (e.g., routers). Typically, a LID will be a randomly generated bit combination (e.g., 256-bit hash value).
  • the further aspect of the invention introduces the concept of a “Link ID Tag” (LIT), as a compact representation of a Link ID.
  • LIT Link ID Tag
  • every link ID is associated with a set of d LITs that are computed by applying a multi-valued mapping function to each LID, so that the LITs are computed in the same way for each link ID.
  • d is a system parameter that can be optimized depending on the network. A typical range of d would be from 2 to 32.
  • the mapping function can be a set of k hash functions that are applied to each Link ID to create, for each Link ID, a LIT bit vector with k bits set to 1 and m-k bits set to 0. Incorporating a LIT of this form into a BF would be equivalent to a m-bit BF with one inserted element using k hash functions. (A description of how the d sets of LITs are obtained is given below.)
  • a Link ID may the form of a bit mask of size m with k bits set to 1 and the other m-k bits set to 0, for convenient BF addition and checking operations.
  • LITs that take the form of a bit mask of size m with k bits set to 1 and the other m-k bits set to 0, and the size and representation of the Link ID is free and can take any suitable form from which the LITs can be computed—thus, this aspect allows greater choice of form for the Link IDs themselves.
  • the generation process of the set of d LITs for a link ID can be a random process or a more controlled process to adapt better to the actual topology of the network.
  • the generation of the LITs for a Link ID may be linked to topology as follows: During the bootstrap process (e.g., a forwarding node attaching to the network), the link IDs are registered with the Topology Module.
  • the LITs can be generated by the forwarding node itself if the hash functions used for the generation of LITs are known by both parties.
  • the Topology Module can return the LITs to the attaching node.
  • FIG. 14 illustrates one possible method of generating LITs for one Link ID, by applying a first hash procedure H 1 (x) to the Link ID to generate the first LIT based on the k bits determined by H 1 (x) to be set to one, by applying a second hash procedure to the Link ID to generate the second LIT and so on until a d th hash function Hd(x) is applied to the Link ID to generate the d th LIT.
  • Each hash procedure consists of k hash functions, each of which determines one bit position in the bit vector that is to be set to one, as described with reference to FIG. 1 above.
  • each hash procedure contains new sets of hash functions, so that no two hash procedures should generate the same output (except by chance).
  • the subsequent hash procedures could be applied iteratively to the previous generated LIT and this would not require that each hash procedure contains new sets of hash functions.
  • the set of k hash functions may remain fixed and be applied iteratively on the last generated LIT—this would be another valid procedure to return good random LITs and save on the amount of hash functions required.
  • only two random functions and two hashing are required to generate all the LITs.
  • link ID Tags there are various ways to determine the link ID Tags. They may be automatically generated by the routers and communicated afterwards to the routing layer, or they may be assigned by other instances and configured on the routers.
  • FIG. 15 is a schematic view of a network node that identifies each output interface with a Link ID (Link IDa for output port 1 , Link IDb for output port 2 , and so on).
  • the node maintains d forwarding tables indexed by Link ID Tags, which identify the output port(s) associated with each LIT.
  • FIG. 16 is a schematic illustration of a packet header having a field that gives the value of d used to generate the Bloom filter that is contained in another field in the packet header.
  • the d LITs can be very efficiently generated by using only two random independent hash functions (e.g., BOB, OAAT, SBOX, Hsieh, TWMX, RS, SHA, MD5) without any increase in the asymptotic false positive probability.
  • any LIT generation process can be compactly represented by the set of i indexes that were used to compute the k positions of the LIT set to 1.Therefore, if h 1 (x) and h 2 (x) are known by the routing elements, only sharing d*k integers i is required to derive the LITs for any LID.
  • the Topology Module could, instead of sending back the whole LITs to the forwarding nodes, just send the indexes i to be used to compute the LITs.
  • the packet header contains a BF that contains or encodes the LITs of the link(s) along which the packet should be forwarded, and also identifies the d value of the BF.
  • packet forwarding may be done by the network node maintain a forwarding table for each of the d representations of link identifiers, as shown in FIG. 15 .
  • the forwarding function in the node selects the forwarding table to be used based on the value d included in the d-enhanced BF forwarding header.
  • the port forwarding operation is straightforward, the BF is AND in parallel against all LIT entries and whenever the LIT entry is obtained as a result of this fast element check operation the packet is forwarded to the PortOut value in the forwarding table.
  • Each look-up table lists the appropriate output port for each Link ID Tag, for example as follows (tables are shown only for two d values):
  • the representation contains d look-up tables as for the case of the standard representation, except that the look-up tables do not store the full LITs but store only the positions of the k bits of the LIT that are set to 1.
  • n the number of link IDs to be represented in the BF.
  • the optimization procedure for the sake of minimizing false positives is as follows. As described above, d LITs are generated for each Link ID, and these are labelled LIT 1 , LIT 2 . . . LITd (steps 1 ( 1 ), 1 ( 2 ), . . . 1 (d) of FIG. 20 ).
  • the Routing function constructing the BF inserts the LIT 1 representation of every link ID in a first candidate Bloom filter BF 1 by simple ORing the LIT 1 s (step 2 ( 1 ) of FIG. 20 ). Similarly, following the same method it inserts the LIT 2 representation of every link ID in a second candidate Bloom filter BF 2 by simple ORing the LIT 2 s (step 2 ( 2 ) of FIG. 20 ), and so on, taking the next LIT representation of every link to be inserted until the d th candidate Bloom filter BFd is constructed by inserting the LITd representation of every link ID (step 2 (d) of FIG. 2 ), resulting in d BFs that represent the same network path(s).
  • the d BFs are constructed in parallel, rather than one after the other as described here.
  • the d BFs represent the same network path(s), owing to the probabilistic nature of the LITs and the OR operation to construct the BF, the BFs will vary regarding the number (and positions) of bits set to 1.
  • the BF to be used in routing packets is selected from the d candidate BFs (step 3 of FIG. 20 ). In one embodiment, the BF that has the lowest overall probability of returning a false positive is selected.
  • the selected Bloom filter may then be used as described in the embodiments above and, for example, may be sent to the source node and assembled into the packet header (steps 6 , 7 of FIG. 12 ).
  • the routing function may send the selected Bloom filter to a node other than the source node.
  • stages may all be performed in the same network node, or they may be spread over two or even three different network nodes or end-host nodes.
  • the method of FIG. 20 were performed wholly in the source node, as suggested above, with the source node then including the selected Bloom filter in a packet header, this would be a case of the generating stage, the selecting stage and the use stage all being carried out in the same node.
  • the routing function could make a preliminary selection from the d Bloom filters, for example discarding from further consideration any Bloom filter that would give false positives for one or more specified links.
  • the routing function would then send those Bloom filters that survived this preliminary selection to the another node (possibly with an indication of which Bloom filter the routing function considers should be selected) for the another node to make the final selection. If the other node were not the intended user of the selected Bloom Filter, the other node would send the selected Bloom filter to the intended user.
  • the probability of a cell being empty depends on the number of cells that have already been set to 1. If the number of bits set to 0 is increased there is more chance of finding a 0 when checking for elements, and consequently the false positive ratio is less.
  • selection of the BF that has the lowest probability of returning a false positive from the d candidate BFs is straightforward—the BF with the most 0's (or smallest number of bits set to 1) will perform better, causing fewer false positives, which in the routing method of the invention results in fewer less links receiving unrequested traffic.
  • the selection algorithm to select the candidate d BF with lowest predicted false positive probability would be: Select d yielding the min ⁇ 0 k , . . . , ⁇ d k ⁇ fpa.
  • k is not required to be the same for each d LIT representation.
  • it can be useful to have different amount k of bits set to one for each LIT representation. For instance, with d 8, we could have a distribution of k like, for example, ⁇ 3;3;4;4;5;5;6;6 ⁇ . That means, two out of the 8 LITs would have only 3 bits set to 1, two LITs would have 4 bits set to one, and so on.
  • the selection algorithm is the described above which is the general case, and not just the minimum number of zeros which only applies when the same k is used for the constructions of all LITs.
  • Table 1 shows, for each candidate BF, not only the overall false positive ratio but the false positive ratio for three sub-sets of particular links (inter-domain links, links in low capacity zones and congested links). It is assumed that a false positive in an inter-domain link, a link in a low capacity zone or in a congested link is more harmful than a false positive in other links.
  • candidate BF 3 has a low overall false positive ratio it gives a high probability of false positive for links in low capacity zones and congested links. It may therefore be desirable to select candidate BF 2 as the BF for the packet header—although candidate BF 2 has a higher overall false positive ratio than candidate BF 3 it gives a lower probability of false positive for links in low capacity zones and congested links.
  • this embodiment allows the BF to be selected on the basis of the probability of a false positive in selected links (in this embodiments for links where a false positive is considered to be is more harmful) rather than on the basis of the overall probability of a false positive.
  • this aspect of the invention provides a powerful method of constructing the forwarding BF for packet headers so as to avoid (or minimise) packets erroneously entering certain network areas owing to the BF returning false positives.
  • Generating d equivalent candidate BFs and selecting one of the candidate BFs guarantees that the essential path(s) of packets through the network is/are maintained, but can minimize false positives over certain links or spread the effects of false positives throughout more convenient paths.
  • the usage of the proposed link ID Tags reduces the false positive rate when a given set of link information is inserted into a probabilistic compact representation such as a Bloom filter. Reduction of false positives results in a more bandwidth efficient solution of the BF-based routing approach.
  • the proposed methods of generating LITs and selecting the most appropriate BF significantly enhances the performance of the BF-based routing scheme without losing the simplicity of the forwarding process and at a very small implementation cost. Consequently, for a certain maximal false probability value, the proposed construction of BFs based on link ID Tags increases the capacity of link information that can be added to a BF without extending its size.
  • Smart choosing among candidate Link ID Tags representing link IDs not only increases the maximum number of routing hops determined by the BF but also provides more flexibility in controlling the effects of false positives by e.g., preventing (or minimising) false positives in certain network regions identified by LIDs or by e.g., spreading the effects of false positives throughout more convenient paths. This finer control over false positives potentially enables applying routing and security policies to the BF-based source routing approach described herein.
  • FIG. 18 shows the improvement in actual false positive rates of BFs constructed following the d-choice LIT technique.
  • FIG. 18 shows the false positive rate as a function of the number of links encoded in a BF for five cases:
  • the figure shows the average and spread of the false positive rates over 50 experiments per data point (number of elements in the filter).
  • FIG. 19 shows how the improvement in actual false positive rates of BFs constructed following the d-choice LIT technique depends on the value of d.
  • FIG. 19 shows the false positive rate as a function of the number of links encoded in a BF for three different values of d as k is kept constant:
  • the figure shows the average and spread of the false positive rates over 50 experiments per data point (number of elements in the filter).
  • the method of associating d ‘equivalent’ Tags to a unique ID have focused on usage scenarios where the ID refers to some identifier for a network link.
  • the hashing procedure used to generate the Tags from the ID is agnostic to the name form, size or semantics of the ID from which the d-Tags are derived. Therefore, the above-described methods of constructing d candidate BFs are not limited to BFs that encode network links but apply to other use cases where a set of IDs (identifiers) is compactly represented by a probabilistic data structure such as a BF.
  • ID a host name (or any type of host identity, identifier, signature, key, etc) and we want to build a compact representation of a set of host names.
  • d Tags for each of the IDs, compute the d candidate representations (Bloom filters) and apply the selection algorithm appropriate to the particular usage scenario.
  • the basic criteria could be minimizing the false positive probability estimation of the BF, and therefore the selection algorithm would choose the candidate with the lowest number of bits set to one, the best false positive probability after hashing which will depend on how many items where inserted and, on how the Tags were constructed (for example depending on whether every Tag has a fixed number k of bits set to 1 or whether Tags have different cardinality of k).
  • IDs from which Tags can be constructed include network domains (administrative and physical domains), networking systems, application processes, network interfaces, logical and virtual ports, and so on. Complex optimization strategies and specific selection criteria may be defined depending on the application, while the basic construction methods of the d Tags and d candidate BFs could be directly applied as well as or instead of a simple false positive ratio mitigation algorithm.

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)
US13/059,958 2008-08-26 2008-10-10 Packet forwarding in a network Expired - Fee Related US8559434B2 (en)

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
EPPCT/EP2008/061167 2008-08-26
PCT/EP2008/061167 WO2010022767A1 (en) 2008-08-26 2008-08-26 Packet forwarding in a network
PCT/EP2008/063647 WO2010022799A1 (en) 2008-08-26 2008-10-10 Packet forwarding in a network

Related Parent Applications (1)

Application Number Title Priority Date Filing Date
PCT/EP2008/061167 Continuation-In-Part WO2010022767A1 (en) 2008-08-26 2008-08-26 Packet forwarding in a network

Publications (2)

Publication Number Publication Date
US20110149973A1 US20110149973A1 (en) 2011-06-23
US8559434B2 true US8559434B2 (en) 2013-10-15

Family

ID=40548574

Family Applications (1)

Application Number Title Priority Date Filing Date
US13/059,958 Expired - Fee Related US8559434B2 (en) 2008-08-26 2008-10-10 Packet forwarding in a network

Country Status (5)

Country Link
US (1) US8559434B2 (de)
JP (1) JP5214804B2 (de)
CN (1) CN102132533A (de)
AT (1) ATE538569T1 (de)
WO (2) WO2010022767A1 (de)

Cited By (12)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20130227092A1 (en) * 2009-04-21 2013-08-29 Techguard Security, Llc Methods of structuring data, pre-compiled exception list engines and network appliances
US9342691B2 (en) 2013-03-14 2016-05-17 Bandura, Llc Internet protocol threat prevention
US9894093B2 (en) 2009-04-21 2018-02-13 Bandura, Llc Structuring data and pre-compiled exception list engines and internet protocol threat prevention
US9900249B2 (en) 2009-09-14 2018-02-20 Nec Corporation Communication system, forwarding node, path management server, communication method, and program
US10313240B2 (en) * 2017-06-26 2019-06-04 Intel Corporation Technologies for efficient network flow classification with vector bloom filters
US10402172B1 (en) 2019-02-28 2019-09-03 Qrypt, Inc. Multi-source entropy and randomness aggregation and distribution network
US20190327337A1 (en) * 2018-04-19 2019-10-24 Futurewei Technologies, Inc. Secure and Reliable On-Demand Source Routing in an Information Centric Network
US10772036B2 (en) * 2016-07-07 2020-09-08 Idac Holdings, Inc. Procedures for dynamically configured network coding based multi-source packet transmission utilizing ICN
US10812280B2 (en) 2016-07-01 2020-10-20 Idac Holdings, Inc. Enabling HTTP content integrity for co-incidental multicast delivery in information-centric networks
US10979482B2 (en) 2015-01-30 2021-04-13 Idac Holdings, Inc. Methods and systems for anchoring hypertext transfer protocol (HTTP) level services in an information centric network (ICN)
US11646993B2 (en) 2016-12-14 2023-05-09 Interdigital Patent Holdings, Inc. System and method to register FQDN-based IP service endpoints at network attachment points
US11811642B2 (en) 2018-07-27 2023-11-07 GoTenna, Inc. Vine™: zero-control routing using data packet inspection for wireless mesh networks

Families Citing this family (67)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP2168325B1 (de) * 2007-06-14 2010-12-15 Telefonaktiebolaget LM Ericsson (publ) Routing in einem netzwerk
JP5551772B2 (ja) 2009-06-09 2014-07-16 テレフオンアクチーボラゲット エル エム エリクソン（パブル） ネットワークにおけるパケット転送
CN102714839A (zh) * 2010-01-29 2012-10-03 瑞典爱立信有限公司 网络中的分组路由选择
CN102804715B (zh) * 2010-03-17 2016-11-09 日本电气株式会社 通信系统、节点、控制服务器以及通信方法
JP5424988B2 (ja) * 2010-06-04 2014-02-26 日本電信電話株式会社 マルチキャスト転送方法、パケット転送システム、ノード装置及びパケット転送プログラム
JP2012054753A (ja) * 2010-09-01 2012-03-15 Nec Corp 光通信システムおよびノード装置
CN102333036B (zh) * 2011-10-17 2015-06-03 中兴通讯股份有限公司 一种实现高速路由查找的方法和系统
CN102609446B (zh) * 2012-01-05 2013-12-25 厦门市美亚柏科信息股份有限公司 一种分布式Bloom过滤系统及其使用方法
JP5624579B2 (ja) * 2012-03-23 2014-11-12 株式会社東芝 オンチップルータ
KR20130140932A (ko) * 2012-05-08 2013-12-26 한국전자통신연구원 네트워크 경로 계산장치, 콘텐츠 요청노드, 중계노드 및 이를 포함하는 정보 중심 네트워크 시스템과 이를 이용한 네트워크 경로 계산방법
US9071533B2 (en) * 2012-07-31 2015-06-30 Cisco Technology, Inc. Multicast group assignment using probabilistic approximations
US9300569B2 (en) * 2012-07-31 2016-03-29 Cisco Technology, Inc. Compressing data packet routing information using bloom filters
JP6135078B2 (ja) * 2012-09-14 2017-05-31 富士通株式会社 到達確認メッセージについての情報処理方法及び情報処理装置
US9112805B2 (en) * 2012-09-28 2015-08-18 Cisco Technology, Inc. Routing messages in a computer network using deterministic and probabilistic source routes
US9049233B2 (en) 2012-10-05 2015-06-02 Cisco Technology, Inc. MPLS segment-routing
US10419334B1 (en) 2012-12-27 2019-09-17 Sitting Man, Llc Internet protocol routing methods, systems, and computer program products
US10419335B1 (en) 2012-12-27 2019-09-17 Sitting Man, Llc Region scope-specific outside-scope indentifier-equipped routing methods, systems, and computer program products
US10904144B2 (en) 2012-12-27 2021-01-26 Sitting Man, Llc Methods, systems, and computer program products for associating a name with a network path
US10397100B1 (en) 2012-12-27 2019-08-27 Sitting Man, Llc Routing methods, systems, and computer program products using a region scoped outside-scope identifier
US10447575B1 (en) 2012-12-27 2019-10-15 Sitting Man, Llc Routing methods, systems, and computer program products
US10411997B1 (en) 2012-12-27 2019-09-10 Sitting Man, Llc Routing methods, systems, and computer program products for using a region scoped node identifier
US10404582B1 (en) 2012-12-27 2019-09-03 Sitting Man, Llc Routing methods, systems, and computer program products using an outside-scope indentifier
US10397101B1 (en) 2012-12-27 2019-08-27 Sitting Man, Llc Routing methods, systems, and computer program products for mapping identifiers
US10587505B1 (en) 2012-12-27 2020-03-10 Sitting Man, Llc Routing methods, systems, and computer program products
US10411998B1 (en) 2012-12-27 2019-09-10 Sitting Man, Llc Node scope-specific outside-scope identifier-equipped routing methods, systems, and computer program products
US10404583B1 (en) 2012-12-27 2019-09-03 Sitting Man, Llc Routing methods, systems, and computer program products using multiple outside-scope identifiers
US10212076B1 (en) 2012-12-27 2019-02-19 Sitting Man, Llc Routing methods, systems, and computer program products for mapping a node-scope specific identifier
US10374938B1 (en) 2012-12-27 2019-08-06 Sitting Man, Llc Routing methods, systems, and computer program products
US10476787B1 (en) 2012-12-27 2019-11-12 Sitting Man, Llc Routing methods, systems, and computer program products
US9537718B2 (en) 2013-03-15 2017-01-03 Cisco Technology, Inc. Segment routing over label distribution protocol
JP6146153B2 (ja) * 2013-06-18 2017-06-14 富士通株式会社 情報処理方法、装置及びプログラム
US9806897B2 (en) 2013-09-17 2017-10-31 Cisco Technology, Inc. Bit indexed explicit replication forwarding optimization
US9853822B2 (en) 2013-09-17 2017-12-26 Cisco Technology, Inc. Bit indexed explicit replication
US10461946B2 (en) 2013-09-17 2019-10-29 Cisco Technology, Inc. Overlay signaling for bit indexed explicit replication
US10003494B2 (en) 2013-09-17 2018-06-19 Cisco Technology, Inc. Per-prefix LFA FRR with bit indexed explicit replication
US11451474B2 (en) 2013-09-17 2022-09-20 Cisco Technology, Inc. Equal cost multi-path with bit indexed explicit replication
US10218524B2 (en) 2013-09-17 2019-02-26 Cisco Technology, Inc. Bit indexed explicit replication for layer 2 networking
US9762488B2 (en) 2014-03-06 2017-09-12 Cisco Technology, Inc. Segment routing extension headers
US9699071B2 (en) 2014-04-28 2017-07-04 Huawei Technologies Co., Ltd. Centrally optimized variable length coding for source routed multicast
JP6451116B2 (ja) * 2014-07-16 2019-01-16 富士電機株式会社 無線通信システム、無線通信方法、ソースルーチング方式の無線機識別符号短縮方法
US9807001B2 (en) 2014-07-17 2017-10-31 Cisco Technology, Inc. Segment routing using a remote forwarding adjacency identifier
JP2016063479A (ja) * 2014-09-19 2016-04-25 株式会社東芝 管理装置、通信装置、管理システム、管理方法、およびプログラム
GB2537338A (en) 2014-11-28 2016-10-19 Aria Networks Ltd Modeling a border gateway protocol network
WO2016093749A1 (en) * 2014-12-09 2016-06-16 Telefonaktiebolaget Lm Ericsson (Publ) Routing in wireless ad-hoc networks
US9906378B2 (en) 2015-01-27 2018-02-27 Cisco Technology, Inc. Capability aware routing
US10341221B2 (en) 2015-02-26 2019-07-02 Cisco Technology, Inc. Traffic engineering for bit indexed explicit replication
CN105162594B (zh) * 2015-07-31 2018-03-30 飞天诚信科技股份有限公司 一种快速签名方法及签名设备
CN106506355B (zh) * 2015-09-07 2020-06-19 中兴通讯股份有限公司 多路径路由的管理方法及装置
US10263881B2 (en) 2016-05-26 2019-04-16 Cisco Technology, Inc. Enforcing strict shortest path forwarding using strict segment identifiers
US11032197B2 (en) 2016-09-15 2021-06-08 Cisco Technology, Inc. Reroute detection in segment routing data plane
US10630743B2 (en) 2016-09-23 2020-04-21 Cisco Technology, Inc. Unicast media replication fabric using bit indexed explicit replication
US10412005B2 (en) * 2016-09-29 2019-09-10 International Business Machines Corporation Exploiting underlay network link redundancy for overlay networks
US10637675B2 (en) 2016-11-09 2020-04-28 Cisco Technology, Inc. Area-specific broadcasting using bit indexed explicit replication
US10587491B1 (en) 2016-12-27 2020-03-10 Amazon Technologies, Inc. Testing computer networks in real time
US11076025B1 (en) * 2016-12-27 2021-07-27 Amazon Technologies, Inc. Generating network packet centric signatures
US10659571B1 (en) 2016-12-27 2020-05-19 Amazon Technologies, Inc. Network device with integrated packet generators or packet checkers
US10666775B1 (en) 2016-12-27 2020-05-26 Amazon Technologies, Inc. Integrated packet generator and checker
US10447496B2 (en) 2017-03-30 2019-10-15 Cisco Technology, Inc. Multicast traffic steering using tree identity in bit indexed explicit replication (BIER)
US10164794B2 (en) 2017-04-28 2018-12-25 Cisco Technology, Inc. Bridging of non-capable subnetworks in bit indexed explicit replication
IL315283A (en) * 2018-03-30 2024-10-01 Google Llc Arbitrating portions of transactions over virtual channels associated with an interconnect
JP7383631B2 (ja) 2018-03-30 2023-11-20 グーグル エルエルシー システムオンチップ（ＳｏＣ）エージェントのリセットおよび電力管理のためのプロトコルレベル制御
US11012414B2 (en) 2019-04-30 2021-05-18 Centripetal Networks, Inc. Methods and systems for prevention of attacks associated with the domain name system
US11012417B2 (en) 2019-04-30 2021-05-18 Centripetal Networks, Inc. Methods and systems for efficient packet filtering
US11140074B2 (en) 2019-09-24 2021-10-05 Cisco Technology, Inc. Communicating packets across multi-domain networks using compact forwarding instructions
KR102681031B1 (ko) * 2019-11-22 2024-07-04 센트리페탈 리미티드 도메인 네임 시스템과 연관된 공격을 방지하기 위한 방법 및 시스템
US11853577B2 (en) * 2021-09-28 2023-12-26 Hewlett Packard Enterprise Development Lp Tree structure node compaction prioritization
US20250233823A1 (en) * 2024-01-17 2025-07-17 Ciena Corporation Apparatuses and methods for facilitating an active path inventory based on path caching and distribution techniques

Citations (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6341311B1 (en) 1998-05-29 2002-01-22 Microsoft Corporation Directing data object access requests in a distributed cache
US20020131418A1 (en) 2001-03-14 2002-09-19 Michael Raftelis Method and apparatus for establishing a path identifier in a communication network
US20040190517A1 (en) * 2003-03-31 2004-09-30 Anupam Gupta Method and apparatus for routing a packet within a plurality of nodes arranged in a line or a tree given a maximum stack depth
WO2006020658A1 (en) 2004-08-09 2006-02-23 Johnny Yau Method and apparatus for ad hoc mesh routing
US20060268911A1 (en) * 2003-05-30 2006-11-30 Johannes Bergmann Method for routing ip-packets to an external control comonent of a network node in an ip-packet switching communications network comprising several network nodes
US7826369B2 (en) * 2009-02-20 2010-11-02 Cisco Technology, Inc. Subsets of the forward information base (FIB) distributed among line cards in a switching device

Family Cites Families (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7526807B2 (en) * 2003-11-26 2009-04-28 Alcatel-Lucent Usa Inc. Distributed architecture for statistical overload control against distributed denial of service attacks
US20060165053A1 (en) * 2005-01-21 2006-07-27 Nec Laboratories America, Inc. Content based data packet routing using labels
JP4732972B2 (ja) * 2006-06-30 2011-07-27 株式会社エヌ・ティ・ティ・ドコモ アドホックネットワーク、ノード、経路制御方法、及び経路制御プログラム
US7813350B2 (en) * 2006-10-23 2010-10-12 Cisco Technology, Inc. System and method to process data packets in a network using stateful decision trees
CN101087305B (zh) * 2007-07-09 2010-09-08 中国人民解放军国防科学技术大学 大规模非结构化p2p网络中的资源搜索方法
CN100531102C (zh) * 2007-11-02 2009-08-19 华为技术有限公司 路由表调整方法、路由查询方法和装置及路由表存储装置

Patent Citations (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6341311B1 (en) 1998-05-29 2002-01-22 Microsoft Corporation Directing data object access requests in a distributed cache
US20020131418A1 (en) 2001-03-14 2002-09-19 Michael Raftelis Method and apparatus for establishing a path identifier in a communication network
US20040190517A1 (en) * 2003-03-31 2004-09-30 Anupam Gupta Method and apparatus for routing a packet within a plurality of nodes arranged in a line or a tree given a maximum stack depth
US20060268911A1 (en) * 2003-05-30 2006-11-30 Johannes Bergmann Method for routing ip-packets to an external control comonent of a network node in an ip-packet switching communications network comprising several network nodes
WO2006020658A1 (en) 2004-08-09 2006-02-23 Johnny Yau Method and apparatus for ad hoc mesh routing
US7826369B2 (en) * 2009-02-20 2010-11-02 Cisco Technology, Inc. Subsets of the forward information base (FIB) distributed among line cards in a switching device

Non-Patent Citations (9)

* Cited by examiner, † Cited by third party
Title
Aad et al. "Packet Coding for Strong Anonymity in Ad Hoc Networks" 2006 Securecomm and Workshops, pp. 1-10, Aug. 1, 2006.
Bao "A New Approach to Anonymous Multicast Routing in Ad Hoc Networks" Second International Conference, IEEE, Piscataway, NJ, pp. 1-12, Aug. 22, 2007.
Castelluccia et al. "Hash-Based Dynamic Source Routing" Networking, LNCS 3042, pp. 1012-1023, 2004.
International Search Report corresponding to PCT Application No. PCT/EP2008/063647, Date of Mailing: Aug. 14, 2009.
Jimeno et al. "A Power Management Proxy with a New Best-of-N Bloom Filter Design to Reduce False Positive" Performance, Computing, and Communications Conference, IEEE, pp. 125-133, Apr. 1, 2007.
Kumar et al. "Segmented Hash: An Efficient Hash Table Implementation for High Performance Networking Subsystems" Symposium on Architecture for Networking and Communications Systems, Piscataway, NJ, pp. 91-103, Oct. 26, 2005.
Notification of Transmittal of the International Preliminary Report on Patentability corresponding to PCT/EP2008/063647, Date of Mailing: Nov. 17, 2008.
Sy et al. "ODAR: On-Demand Anonymous Routing in Ad Hoc Networks" 2006 IEEE International Conference, pp. 267-276, Oct. 1, 2006.
Written Opinion of the International Searching Authority corresponding to PCT/EP2008/063647, Date of Mailing: Aug. 14, 2009.

Cited By (18)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US10764320B2 (en) 2009-04-21 2020-09-01 Bandura Cyber, Inc. Structuring data and pre-compiled exception list engines and internet protocol threat prevention
US9225593B2 (en) * 2009-04-21 2015-12-29 Bandura, Llc Methods of structuring data, pre-compiled exception list engines and network appliances
US20160094381A1 (en) * 2009-04-21 2016-03-31 Bandura, Llc Methods of structuring data, pre-compiled exception list engines, and network appliances
US9894093B2 (en) 2009-04-21 2018-02-13 Bandura, Llc Structuring data and pre-compiled exception list engines and internet protocol threat prevention
US10135857B2 (en) 2009-04-21 2018-11-20 Bandura, Llc Structuring data and pre-compiled exception list engines and internet protocol threat prevention
US20130227092A1 (en) * 2009-04-21 2013-08-29 Techguard Security, Llc Methods of structuring data, pre-compiled exception list engines and network appliances
US9900249B2 (en) 2009-09-14 2018-02-20 Nec Corporation Communication system, forwarding node, path management server, communication method, and program
US9342691B2 (en) 2013-03-14 2016-05-17 Bandura, Llc Internet protocol threat prevention
US10979482B2 (en) 2015-01-30 2021-04-13 Idac Holdings, Inc. Methods and systems for anchoring hypertext transfer protocol (HTTP) level services in an information centric network (ICN)
US10812280B2 (en) 2016-07-01 2020-10-20 Idac Holdings, Inc. Enabling HTTP content integrity for co-incidental multicast delivery in information-centric networks
US10772036B2 (en) * 2016-07-07 2020-09-08 Idac Holdings, Inc. Procedures for dynamically configured network coding based multi-source packet transmission utilizing ICN
US11646993B2 (en) 2016-12-14 2023-05-09 Interdigital Patent Holdings, Inc. System and method to register FQDN-based IP service endpoints at network attachment points
US10313240B2 (en) * 2017-06-26 2019-06-04 Intel Corporation Technologies for efficient network flow classification with vector bloom filters
US20190327337A1 (en) * 2018-04-19 2019-10-24 Futurewei Technologies, Inc. Secure and Reliable On-Demand Source Routing in an Information Centric Network
US10986209B2 (en) * 2018-04-19 2021-04-20 Futurewei Technologies, Inc. Secure and reliable on-demand source routing in an information centric network
US11811642B2 (en) 2018-07-27 2023-11-07 GoTenna, Inc. Vine™: zero-control routing using data packet inspection for wireless mesh networks
US10402172B1 (en) 2019-02-28 2019-09-03 Qrypt, Inc. Multi-source entropy and randomness aggregation and distribution network
US12045583B2 (en) 2019-02-28 2024-07-23 Qrypt, Inc. Multi-source entropy randomness aggregation and distribution network

Also Published As

Publication number Publication date
WO2010022799A1 (en) 2010-03-04
US20110149973A1 (en) 2011-06-23
WO2010022767A1 (en) 2010-03-04
JP2012501127A (ja) 2012-01-12
JP5214804B2 (ja) 2013-06-19
CN102132533A (zh) 2011-07-20
ATE538569T1 (de) 2012-01-15

Similar Documents

Publication Publication Date Title
US8559434B2 (en) Packet forwarding in a network
US8149736B2 (en) Distributed storage of routing information in a link state protocol controlled network
CN101395594B (zh) 用于计算机网络中ip骨干上的数据流的最优路由的技术
US9825860B2 (en) Flow-driven forwarding architecture for information centric networks
KR960014987B1 (ko) 메시지의 멀티캐스트 방법 및 시스템
EP2869511B1 (de) Weiterleitung von paketen auf hash-basis mit hierarchisch strukturierten identifikatoren mit variabler länge über ethernet
CN106559340A (zh) 具有小多径或单径转发状态的以信息为中心的网络
JP2006517077A (ja) 集中管理なしの、匿名の信頼しない当事者間のセキュア通信およびリソース共用の方法および装置
US20120300781A1 (en) Packet Routing in a Network
KR20170038148A (ko) 상태 비유지 정보 중심 네트워킹을 위한 시스템 및 방법
Jain et al. Viro: A scalable, robust and namespace independent virtual id routing for future networks
CN101394339A (zh) 一种在对等网络中实现路由的方法、系统及装置
US20190327337A1 (en) Secure and Reliable On-Demand Source Routing in an Information Centric Network
EP2319215B1 (de) Paketweiterleitung in einem netzwerk
Zahemszky et al. Exploring the pub/sub routing & forwarding space
Nguyen et al. Conat: A network coding-based interest aggregation in content centric networks
Gashi Path protection switching in information centric networking
Vassilakis et al. Mediator-assisted multi-source routing in information-centric networks
Sehgal et al. A flexible concast-based grouping service
Marandi Bloom Filter-Based Content Discovery and Retrieval for Information-Centric Networks.
US20090196300A1 (en) Method for forwarding data packets and communication network having flooding transport properties
Westphal DUPLEX: An Architecture for a Data-Universal Plane for Information Exchange
Bikfalvi Nozzilla: A Novel Peer to Peer Architecture for Video Streaming

Legal Events

Date Code Title Description
AS Assignment

Owner name: TELEFONAKTIEBOLAGET LM ERICSSON (PUBL), SWEDEN

Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:JOKELA, PETRI;ESTEVE, CHRISTIAN;KJALLMAN, JIMMY;AND OTHERS;SIGNING DATES FROM 20090113 TO 20090206;REEL/FRAME:025835/0814

CC Certificate of correction
REMI Maintenance fee reminder mailed
LAPS Lapse for failure to pay maintenance fees

Free format text: PATENT EXPIRED FOR FAILURE TO PAY MAINTENANCE FEES (ORIGINAL EVENT CODE: EXP.)

STCH Information on status: patent discontinuation

Free format text: PATENT EXPIRED DUE TO NONPAYMENT OF MAINTENANCE FEES UNDER 37 CFR 1.362

FP Lapsed due to failure to pay maintenance fee

Effective date: 20171015