Packet Forwarding In A Network
1 Assignment
0 Petitions
Accused Products
Abstract
A method of providing packet routing information comprises: encoding routing information from a source node to one or more destination nodes into a compact representation of set membership; and putting the compact representation of sets into a header of a packet that is to be sent from the source node to the destination node(s). The compact representation may be obtained by: generating d representations of a set of identifiers; generating d candidate compact representations of set membership from the d representations of the identifiers; and selecting one of the candidate compact representation of set membership. The selection may be made on the basis of which of the candidate compact representations has the lowest rate of returning false positives.
85 Citations
31 Claims
-
1-24. -24. (canceled)
-
25. A method of providing packet routing information, the method comprising:
-
encoding routing information from a source node to one or more destination nodes into a compact representation of set membership; wherein the routing information comprises representations of one or more identifiers, each identifier identifying a respective network link, a respective node, or a full or partial path containing two or more network links; and wherein the method comprises generating d candidate compact representations of set membership from d representations of the one or more identifiers, where d is n integer greater than one, and putting one of the compact representations of set membership into the header of a packet that is to be sent from the source node to the destination node(s). - View Dependent Claims (26, 27)
-
-
28. A method of routing a packet through a network, the method comprising:
-
receiving a packet at a network node; 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 to determine one or more other nodes to which the packet is to be sent from the node; and forwarding the packet along the determined link(s) and/or to the determined other node(s); wherein the routing information comprises one of a plurality of candidate representations of one or more identifiers, each identifier identifying a respective network link, a respective node, or a full or partial path containing two or more network links; and wherein the routing further comprises selecting, from d look-up tables each corresponding to one of d candidate representations of the one or more identifiers, where d is an integer greater than one, a look-up table corresponding to the received representation of the one or more identifiers.
-
-
29. A network node comprising:
-
means for receiving a packet; and 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 links to which the packet is to be sent from the node; the network node being adapted to forward the packet along the determined link(s) and/or to the determined other node(s); wherein the network node is further adapted to select, from d look-up tables each corresponding to one of d candidate representations of the one or more identifiers, where d is an integer greater than one, a look-up table corresponding to the received representation of the one or more identifiers.
-
-
30. 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 routing information comprising representations of one or more identifiers;
-
wherein the network node is adapted to encode routing information by; generating d representations of at least some of the identifiers, where d is an integer greater than one; generating d candidate compact representations of set membership from the d representations of the identifiers; and selecting one of the candidate compact representation of set membership. - View Dependent Claims (31)
-
Specification