Planning routes and allocating identifiers to routes in a managed frame-forwarding network
A method is provided of planning routes and allocating route identifiers in a managed frame-forwarding network. The network comprises a plurality of nodes interconnected by links, with each node being arranged to forward data frames according to a combination of an identifier and a network address carried by a received data frame and forwarding instructions stored at the node. A first step of the method identifies a sub-set of nodes which are core nodes of the network. The remaining nodes are termed outlying nodes. A spanning tree is then built off each of the identified core nodes, with the spanning tree stopping one link short of any other core node. Each spanning tree defines a loop-free path between a core node at the root of the spanning tree and a set of outlying nodes. Connections are planned between roots of the spanning trees and a different identifier is allocated to each planned connection between a pair of spanning trees.
1. A method of planning routes and allocating route identifiers in a managed frame-forwarding network, the network comprising a set of nodes interconnected by links, with each node being arranged to forward data frames according to a combination of a route identifier and a network address carried by a received data frame and forwarding instructions stored at the node, the method comprising:
identifying a sub-set of the nodes which are core nodes of the network, the remaining nodes being outlying nodes;
building a spanning tree off each of the identified core nodes, with the spanning tree stopping one link short of any other core node, the spanning tree having a root, and the spanning tree defining a loop-free path between the core node at the root of the spanning tree and a set of outlying nodes; and,
planning connections between roots of the spanning trees and allocating a different route identifier to each planned connection between a pair of spanning trees,
wherein building the spanning tree off each of the identified core nodes is arranged such that where an outlying node is served by spanning trees rooted on two different core nodes, the paths of the two spanning trees are differently directed to that outlying node,
wherein building the spanning tree uses a metric associated with each link and wherein, if the spanning trees provide paths which are co-directed, the value of the metric associated with the co-directed link is adjusted to ensure that on a subsequent iteration of building the spanning trees the paths of the two spanning trees are differently directed.
2. A method according to claim 1 wherein the step of planning connections between roots of the spanning trees plans a set of connections which minimises the number of single points of failure common to more than one different connection between each pair of outlying nodes.
3. A method according to claim 1 wherein the step of identifying core nodes in the network comprises identifying a core node as a node which is connected to at least N other nodes.
4. A method according to claim 1 wherein the identifier is the same for both directions of information transfer along a bi-directional co-routed path between two nodes and the step of planning connections between the roots of pairs of the spanning trees connects each spanning tree with every other spanning tree and allocates a different route identifier to each planned connection.
5. A method according to claim 4 wherein the step of allocating route identifiers must only allocate a different route identifier to a connection between a pair of spanning trees where the outlying nodes served by either of the spanning trees in the pair overlap with any of the outlying nodes served by another spanning tree.
6. A method according to claim 4 wherein the route identifier is an Ethernet VLAN ID and the network address is an Ethernet Destination Address.
7. A method of planning routes and allocating route identifiers in a managed frame-forwarding network, the network comprising a set of nodes interconnected by links, with each node being arranged to forward data frames according to a combination of a route identifier and a network address carried by a received data frame and forwarding instructions stored at the node, the method comprising:
identifying a sub-set of the nodes which are core nodes of the network, the remaining nodes being outlying nodes;
building a spanning tree off each of the identified core nodes, with the spanning tree stopping one link short of any other core node, the spanning tree having a root, and the spanning tree defining a loop-free path between the core node at the root of the spanning tree and a set of outlying nodes; and,
planning connections between roots of the spanning trees and allocating a different route identifier to each planned connection between a pair of spanning trees,
wherein the route identifier is different in each direction of information transfer along a co-routed path between two nodes and the step of planning connections between the roots of pairs of the spanning trees allocates a different route identifier to each spanning tree for use when a data frame must egress the core node which is the root of that tree, the allocated route identifier being associated with ingress at a particular core node and wherein a further route identifier is allocated to each desired route between each ingress core node and the egress core node.
8. A method according to claim 7 wherein if a first spanning tree rooted on an ingress core node has a set of outlying nodes which are distinct from the set of outlying nodes of a second spanning tree rooted on a second ingress core node, a common route identifier can be allocated to routes from those ingress core nodes to any egress core node.
9. A method according to claim 8 wherein the identifier is an Ethernet VLAN ID and the network address is an Ethernet Destination Address.
10. A method according to claim 7 wherein if a first spanning tree has a set of outlying nodes which are distinct from the set of outlying nodes of a second spanning tree, a common identifier can be allocated to the first and second spanning trees for use when a data frame must egress the core node which is the root of either of those trees.
11. A network entity which is arranged to plan routes and allocate route identifiers in a managed frame-forwarding network, the network comprising a set of nodes interconnected by links, with each node being arranged to forward data frames according to a combination of a route identifier and a network address carried by a received data frame and forwarding instructions stored at the node, the network entity being arranged to:
identify a sub-set of the nodes which are core nodes of the network, the remaining nodes being outlying nodes;
build a spanning tree off each of the identified core nodes, with the spanning tree stopping one link short of any other core node, the spanning tree having a root, and the spanning tree defining a loop-free path between the core node at a root of the spanning tree and a set of outlying nodes; and
plan connections between roots of the spanning trees and allocating a different route identifier to each planned connection between a pair of spanning trees,
wherein the network entity is arranged to build the spanning tree off each of the identified core nodes such that where an outlying node is served by spanning trees rooted on two different core nodes, the paths of the two spanning trees are differently directed to that outlying node,
wherein the network entity is arranged to build the spanning tree using a metric associated with each link and wherein, if the spanning trees provide paths which are co-directed, the network entity is arranged to adjust the value of the metric associated with the co-directed link to ensure that on a subsequent iteration of building the spanning trees the paths of the two spanning trees are differently directed.