Patent ID: 8761022

Claim:
A method of selecting a path for use in forwarding packets at a node of a packet-forwarding network, each node of the network having a unique node identifier, the method comprising: determining lowest cost paths between a first node of the network and a second node of the network; determining that a plurality of lowest cost paths have substantially equal cost; and selecting a lowest cost path from the plurality of lowest cost paths having substantially equal cost, the selected lowest cost path being a path that would be selected by: for each lowest cost path, sorting respective node identifiers assigned to nodes traversed by the lowest cost path according to a first ordering criterion to derive a respective path identifier; ordering the path identifiers according to a second ordering criterion; and selecting a lowest cost path having its path identifier at one extreme of the ordered path identifiers; wherein the first ordering criterion and the second ordering criterion meet a condition selected from: (1) the first ordering criterion is an increasing ordering and the second ordering criterion is a modified lexicographic ordering which, when the path identifier for a first path is a prefix of the path identifier for a second path, orders the second path before the first path; and (2) the first ordering criterion is a decreasing ordering and the second ordering criterion is a lexicographic ordering which, when the path identifier for a first path is a prefix of the path identifier for a second path, orders the first path before the second path.