Patent Document ID: 9973442
Application ID: 14869168
Patent Flag: 1

Claim One:
1. A method, implemented by a controller device, for calculating reachability matrices for a multi-stage network comprising a plurality of tiers, the method comprising: receiving, by the controller device, link status information from network devices of the multi-stage network, wherein each tier, of the plurality of tiers, comprises a plurality of network devices, wherein each network device is a switch or a router, and wherein the multi-stage network is represented by an unfolded multi-stage network having a plurality of stages; for each pair of adjacent stages, of the plurality of stages: determining, by the controller, a binary link state matrix between the pair of adjacent stages from the link status information; calculating, by the controller using one or more matrix multiplication operations, a set of reachability matrices for one or more destination devices, wherein the set of reachability matrices comprises a separate binary reachability matrix for each stage, of the plurality of stages, representing which network devices of the stage can forward network packets to the one or more destination devices; and sending, by the controller device, the set of reachability matrices to the network devices of the multi-stage network; wherein the network devices of the multi-stage network use the set of reachability matrices to make network packet forwarding decisions for the one or more destination devices.