Patent ID: 8310957

Claim:
A method for establishing a multicast distribution tree in a network, the method comprising: constructing a graph of unicast tunnels that connect a set of edge routers that will distribute multicast traffic in the network, wherein the graph comprises a plurality of vertices and a plurality of edges connecting one or more vertex pairs, wherein each one of the plurality of vertices represents a different one of the edge routers, wherein each one of the plurality of edges that connects a vertex pair represents the unicast tunnel that connects the edge routers represented by the vertex pair, and wherein each edge has a metric value for a property of the represented unicast tunnel; calculating a minimum-cost spanning tree for the graph of unicast tunnels based on the edge metric values for the edges, wherein the minimum-cost spanning tree includes the plurality of vertices and a selected subset of the plurality of edges, wherein the minimum-cost spanning tree includes a first vertex that represents an ingress one of the set of edge routers for the multicast traffic and a second vertex that shares one of the edges with a third one of the vertices other than the first vertex representing the ingress edge router; and establishing, with a network router, the multicast distribution tree based on the calculated minimum-cost spanning tree to distribute the multicast traffic from the ingress edge router to the edge routers, wherein the establishing, with the network router, the multicast distribution tree based on the minimum-cost spanning tree comprises sending, with the network router, multicast forwarding state to one or more of the set of edge routers to cause the one or more edge routers to install the multicast forwarding state and to replicate and forward multicast traffic according to the multicast distribution tree.