Patent ID: 8681792

Claim:
A method of routing a packet through a network, the method comprising, at a node of the network: (a) receiving the packet, the node having available a plurality of outgoing links, with each of the plurality of outgoing links being associated with at least one link identifier (ID), and at least one of the plurality of outgoing links being associated with a plurality of link IDs, the packet comprising a state variable and routing information, the routing information encoding a set of link IDs associated with respective links forming a path through the network, and the encoding being in the form of a probabilistic data structure used to test whether a link ID is a member of the set of link IDs, the test having a possibility of a false positive; (b) for each of the plurality of outgoing links: (i) responsive to the outgoing link having more than one associated link ID, using the state variable from the received packet to determine which link ID to use as the associated link ID for the purpose of step (b)(ii); and (ii) testing the data structure for membership of the outgoing link's associated link ID; (c) determining a new state variable based at least partly on the state variable from the received packet; and (d) forwarding the packet along each of the plurality of outgoing links determined in step (b)(ii) to have its associated link ID as a member of the data structure, the packet comprising the routing information and the new state variable.