# US 2009/0080345 A1 · Efficient multipoint distribution tree construction for shortest path bridging > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2009/0080345 A1 - Document ID: US20090080345A1 - Status: Published application - Kind: A1 - Application number: 11/903,451 - Filed: 2007-09-21 - Published: 2009-03-26 - Earliest claimed: 2007-09-21 - Assignees: Ericsson Inc. - Inventors: Eric Ward Gray - Web page: https://patentgrep.com/patent/US20090080345A1 ## CPC - H04Q 3/66: Traffic distributors - H04Q 2213/13056: Routines, finite state machines - H04Q 2213/13138: Least cost routing, LCR - H04Q 2213/13141: Hunting for free outlet, circuit or channel - H04Q 2213/13242: Broadcast, diffusion, multicast, point-to-multipoint (1 : N) - H04Q 2213/13389: LAN, internet - H04Q: SELECTING (switches, relays, selectors H01H; wireless communication networks H04W) ## Abstract A telecommunications system includes a source node. The system includes a plurality of destination nodes. The system includes a network having links and end stations. The system includes a plurality of switches that create paths along links between the source nodes and the destination nodes where there is 100% efficiency along the paths with the paths traversing any link only once to the corresponding destination node from the source node, and the path being a shortest path between the source node and the destination node, where each switch has a Dijkstra computation complexity of O(N) in regard to forming the shortest paths. A method for telecommunications includes the steps of creating paths with a plurality of switches along links of a network between a source node and a plurality of destination nodes where there is 100% efficiency along the paths with the paths traversing any link only once to the corresponding destination node from the source node, and each path being a shortest path between the source node and the destination node, where each switch has a Dijkstra computation complexity of O(N) in regard to forming the shortest paths. There is the step of delivering with the switches frames from the source node to the destination nodes along the shortest paths. ## Claims ### Claim 1 A telecommunications system comprising: a source node; a plurality of destination nodes; a network having links and end stations; and a plurality of switches that create paths along links between the source nodes and the destination nodes where there is 100% efficiency along the paths with the paths traversing any link only once to the corresponding destination node from the source node, and the path being a shortest path between the source node and the destination node, where each switch has a Dijkstra computation complexity of O(N) in regard to forming the shortest paths. ### Claim 2 (depends on 1) A system as described in claim 1 wherein the switches deliver frames from the source node to the destination nodes along the shortest paths. ### Claim 3 (depends on 2) A system as described in claim 2 wherein each switch computes a shortest point to point path from the source node to each destination node, and each switch forms shortest point to multipoint paths from the source node to the destination nodes without additional shortest path computations from the shortest point to point paths. ### Claim 4 (depends on 3) A system as described in claim 3 wherein each switch has a link-state database and establishes unicast paths using the link-state database and shortest path computations. ### Claim 5 (depends on 4) A system as described in claim 4 wherein each switch forwards a special control message to all of the switches having external ports using the corresponding unicast path, where external ports are defined as ports facing a portion of the network containing end stations. ### Claim 6 (depends on 5) A system as described in claim 5 wherein each switch establishes unicast paths for each ingress-egress switch pair defined from each switch with one or more external ports to every other switch also having at least one external port. ### Claim 7 (depends on 6) A system as described in claim 6 wherein the messages are intercepted in each intermediate switch in the network and used to construct a portion of the point to multipoint paths that the respective intermediate switch for the ingress switch that originated the message. ### Claim 8 (depends on 7) A system as described in claim 7 wherein a multipoint distribution tree is constructed by each intermediate switch for each potential ingress switch, with branching added as required for shortest path delivery to the corresponding addressed egress switch. ### Claim 9 (depends on 8) A system as described in claim 8 wherein the messages are only seen at any intermediate switch that is on the shortest path between the ingress switch that originated the message and the egress switch to which it is addressed. ### Claim 10 (depends on 9) A system as described in claim 9 wherein flooding is implemented by using a preliminary determination of whether or not each frame's media access control destination address is known prior to doing a multipoint distribution tree determination by each ingress switch. ### Claim 11 (depends on 10) A system as described in claim 10 wherein only a single multipoint distribution tree is constructed on a per-ingress switch basis at each switch. ### Claim 12 (depends on 11) A system as described in claim 11 wherein no a priori knowledge of a loop-free multipoint distribution tree is required by any switch to construct the shortest paths. ### Claim 13 A method for telecommunications comprising the steps of: creating paths with a plurality of switches along links of a network between a source node and a plurality of destination nodes where there is 100% efficiency along the paths with the paths traversing any link only once to the corresponding destination node from the source node, and each path being a shortest path between the source node and the destination node, where each switch has a Dijkstra computation complexity of O(N) in regard to forming the shortest paths; and delivering with the switches frames from the source node to the destination nodes along the shortest paths. ### Claim 14 (depends on 13) A method as described in claim 13 wherein the creating step includes the step of creating a shortest point to point path from the source node to each destination node by the switches and each switch forms shortest point to multipoint paths from the source node to the destination nodes without additional shortest path computations from the shortest point to point paths. ### Claim 15 (depends on 14) A method as described in claim 14 wherein the creating step includes the step of establishing unicast paths using a link-state database of each switch and shortest path computations. ### Claim 16 (depends on 15) A method as described in claim 15 including the step of forwarding a special control message to all of the switches having external ports using the corresponding unicast path, where external ports are defined as ports facing a portion of the network containing end stations. ### Claim 17 (depends on 16) A method as described in claim 16 wherein the establishing step includes the step of establishing with each switch unicast paths for each ingress-egress switch pair defined from each switch with one or more external ports to every other switch also having at least one external port. ### Claim 18 (depends on 17) A method as described in claim 17 including the steps of intercepting the messages at each intermediate switch in the network and using the messages to construct a portion of the point to multipoint paths that the respective intermediate switch for the ingress switch that originated the message. ### Claim 19 (depends on 18) A method as described in claim 18 including the steps of constructing a multipoint distribution tree by each intermediate switch for each potential ingress switch, and adding branching for shortest path delivery to the corresponding addressed egress switch. ### Claim 20 (depends on 19) A method as described in claim 19 including the step of seeing the messages only at any intermediate switch that is on the shortest path between the ingress switch that originated the message and the egress switch to which it is addressed. ### Claim 21 (depends on 20) A method as described in claim 20 including the step of flooding by using a preliminary determination of whether or not each frame's media access control destination address is known prior to doing a multipoint distribution tree determination by each ingress switch. ### Claim 22 (depends on 21) A method as described in claim 21 including the step of constructing only a single multipoint distribution tree on a per-ingress switch basis at each switch. ### Claim 23 (depends on 22) A method as described in claim 22 wherein the creating step requires no a priori knowledge of a loop-free multipoint distribution tree by any switch to construct the shortest paths. ### Claim 24 A telecommunications system comprising: a source node; a plurality of destination nodes; a network having links and end stations; and a plurality of switches that create paths along links between the source nodes and the destination nodes where there is 100% efficiency along the paths with the paths traversing any link only once to the corresponding destination node from the source node, and the path being a shortest path between the source node and the destination node, where each switch computes a shortest point to point path from the source node to each destination node, and each switch forms shortest point to multipoint paths from the source node to the destination nodes without additional shortest path computations from the shortest point to point paths.