# US 2018/0026850 A1 · Capacity planning in a backbone network > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2018/0026850 A1 - Document ID: US20180026850A1 - Status: Published application - Kind: A1 - Application number: 15/215,328 - Filed: 2016-07-20 - Published: 2018-01-25 - Earliest claimed: 2016-07-20 - Assignees: Facebook, Inc. - Applicants: Facebook, Inc. - Inventors: Josue Israel Kuri Obregon; Nicolas Emilio Stier Moses - Web page: https://patentgrep.com/patent/US20180026850A1 ## CPC - H04L 41/145: {involving simulating, designing, planning or modelling of a network} - G06Q 30/0283: Price estimation or determination - H04L 41/0663: Performing the actions predefined by failover planning, e.g. switching to standby network elements - H04L 41/0896: Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities (flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76) - H04L 41/22: comprising specially adapted graphical user interfaces [GUI] - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) - G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR ## Abstract A system and method for fault-tolerant and long-term network capacity planning is disclosed. The system receives projected data, such as available network supply and network demand, characterizing a backbone network for a set of time periods. The system also receives failure data describing different failure scenarios that may occur. Based on the received network characterization data the system generates a capacity provisioning plan, describing how capacity is added to the backbone network over time, that satisfies the network demand of each time period while providing fault-tolerance under any of the failure scenarios described in the failure data. The capacity provisioning plan is also optimized, based on cost data associated with the backbone network, to minimize total costs. ## Claims ### Claim 1 A method in a computing system, comprising: receiving, at a computing system, demand data characterizing network demand projections for a backbone network, the demand data comprising, for each demand projection, a first node in the backbone network, a second node in the backbone network, a time period, and a projected network demand associated with the first and second nodes for the time period; receiving, at the computing system, supply data characterizing network supply availabilities for the backbone network, the supply data comprising, for each supply availability, a cable in the backbone network comprised of at least one segment, a first node in the backbone network associated with the cable, a second node in the backbone network associated with the cable, a time period, and an available capacity associated with the cable for the time period; receiving, at the computing system, data characterizing network cable costs for the backbone network, the cost data comprising, for each network cable cost, a cable, an upfront cost amount, and a recurring cost amount; receiving, at the computing system, failure data characterizing network failure scenarios, the failure data comprising, for each failure scenario, at least one segment; and identifying needed capacities for the backbone network by: determining, for a set of time periods in the demand data and supply data, a needed capacity for a set of cables in the backbone network by: assigning, for at least some of the failure scenarios in the failure data, a network flow to each cable in the set cables based on the failure scenario, wherein the network flow assigned to a cable is less than or equal to the available capacity for that cable for the time period, and wherein the demand for the time period associated with each pair of first and second nodes is satisfied by the assigned flow between the first and second node; and determining, for each cable in the set of cables, a needed capacity for the cable for the time period based on the network flows assigned to the cable for each of the at least some failure scenarios; and generating, based on the needed capacity for the set of cables at the set of time periods, and the upfront cost amount and recurring cost amount associated with the cables in the set of cables, a capacity provisioning plan comprised of a provisioned capacity for the set of cables at each of the set of time periods. ### Claim 2 (depends on 1) The method of claim 1, further comprising displaying, on a computing system display, an illustration of the provisioned capacity of all cables in the set of cables for a time period. ### Claim 3 (depends on 1) The method of claim 1, further comprising displaying, on a computing system display, an illustration of the needed capacity of all cables in the set of cables for a time period. ### Claim 4 (depends on 1) The method of claim 1, further comprising displaying, on a computing system display, an illustration of the network flow assigned to all cables in the set of cables, based on no failure scenarios, for a time period. ### Claim 5 (depends on 1) The method of claim 1, wherein assigning network flow to each of the cables in the set of cables based on a failure scenario comprises: identifying cables comprised of segments associated with the failure scenario; and assigning no network flow to the identified cables. ### Claim 6 (depends on 1) The method of claim 1, wherein the supply data further comprises, for each supply availability, an asset type characterizing the cable, wherein the asset type may be an investment or a lease, and wherein determining the provisioned capacity for a cable characterized as an investment comprises, for each time period from the set of time periods, setting the provisioned capacity for the cable to greater than or equal to the cable's provisioned capacity for all previous time periods. ### Claim 7 (depends on 1) The method of claim 1, wherein determining the provisioned capacity for each cable in the set of cables for the set of time periods comprises optimizing how much capacity is provisioned from each cable at each time period to minimize a total of costs associated with the set of cables, wherein the cost associated with a cable is based on (1) the upfront cost amount for the cable and (2) the recurring cost amount for the cable and the number of time periods during which capacity is provisioned from that cable. ### Claim 8 (depends on 7) The method of claim 7, wherein minimizing the total of costs associated with all cables is modeled as a multi-commodity flow problem. ### Claim 9 (depends on 7) The method of claim 7, wherein the upfront cost amount comprises a fixed upfront cost amount and a variable upfront cost amount, wherein the recurring cost amount comprises a fixed recurring cost amount and a variable recurring cost amount, and wherein the variable upfront cost amount and the variable recurring cost amount vary based on the provisioned capacity of a cable at a time period. ### Claim 10 (depends on 1) The method of claim 1, wherein the first nodes in the demand data represent sources, the second nodes in the demand data represent destinations, and the projected network demands in the demand data represent demanded bandwidth from the sources to the destinations. ### Claim 11 (depends on 1) The method of claim 1, wherein the first nodes in the supply data represent sources, the second nodes in the supply data represent destinations, and the available capacities in the supply data represent maximum available bandwidth from the sources to the destinations. ### Claim 12 (depends on 1) The method of claim 1, wherein a time period is a fiscal quarter. ### Claim 13 (depends on 1) The method of claim 1, wherein nodes in the supply data and the demand data represent data centers or points of presence in the backbone network. ### Claim 14 (depends on 1) The method of claim 1, wherein the failure data includes failure scenarios, each comprising a single segment, that collectively include every segment in the backbone network. ### Claim 15 A system comprising: an input data processor configured to: receive demand data characterizing network demand projections for a backbone network, the demand data comprising, for each demand projection, a first node in the backbone network, a second node in the backbone network, a time period, and a projected network demand associated with the first and second nodes for the time period; receive supply data characterizing network supply availabilities for the backbone network, the supply data comprising, for each supply availability, a cable in the backbone network comprised of at least one segment, a first node in the backbone network associated with the cable, a second node in the backbone network associated with the cable, a time period, and an available capacity associated with the cable for the time period; receive data characterizing network cable costs for the backbone network, the cost data comprising, for each network cable cost, a cable, an upfront cost amount, a recurring cost amount; and receive failure data characterizing network failure scenarios, the failure data comprising, for each failure scenario, at least one segment; a network flow assignor configured to determine, for each time period in the demand data and supply data, a needed capacity for each of the cables in the backbone network by: assigning, for each of the failure scenarios in the failure data, a network flow to each of the cables based on the failure scenario, wherein the network flow assigned to each cable is less than or equal to the available capacity for that cable for the time period, and wherein the demand for the time period associated with each pair of first and second nodes is satisfied by the assigned flow between the first and second node; and determining, for each cable in the backbone network, a needed capacity for the cable for the time period based on the network flows assigned to the cable for each of the failure scenarios; and a capacity provisioning optimizer configured to generate, based on the needed capacity of each cable in the backbone network for each time period and the upfront cost amount and recurring cost amount associated with each cable, a capacity provisioning plan comprised of a provisioned capacity for each cable at each time period. ### Claim 16 (depends on 15) The system of claim 15, wherein assigning network flow to each of the cables in the backbone network based on a failure scenario comprises: identifying cables comprised of segments associated with the failure scenario; and assigning no network flow to the identified cables. ### Claim 17 (depends on 15) The system of claim 15, wherein the supply data further comprises, for each supply availability, an asset type characterizing the cable, wherein the asset type may be an investment or a lease, and wherein determining the provisioned capacity for a cable characterized as an investment comprises, for each time period, setting the provisioned capacity for the cable to greater than or equal to the cable's provisioned capacity for all previous time periods. ### Claim 18 (depends on 15) The system of claim 15, wherein determining the provisioned capacity for each cable in the backbone network for each time period comprises optimizing how much capacity is provisioned from each cable at each time period to minimize a total of costs associated with all cables, wherein the cost associated with a cable is based on (1) the upfront cost amount for the cable and (2) the recurring cost amount for the cable and the number of time periods during which capacity is provisioned from that cable. ### Claim 19 A computer-readable storage medium storage instructions that, when executed by a computing system, cause the computing system to perform operations comprising: receiving, at a computing system, demand data characterizing network demand projections for a backbone network, the demand data comprising, for each demand projection, a first node in the backbone network, a second node in the backbone network, a time period, and a projected network demand associated with the first and second nodes for the time period; receiving, at the computing system, supply data characterizing network supply availabilities for the backbone network, the supply data comprising, for each supply availability, a cable in the backbone network comprised of at least one segment, a first node in the backbone network associated with the cable, a second node in the backbone network associated with the cable, a time period, and an available capacity associated with the cable for the time period; receiving, at the computing system, cost data characterizing network cable costs for the backbone network, the cost data comprising, for each network cable cost, a cable, an upfront cost amount, and a recurring cost amount; receiving, at the computing system, failure data characterizing network failure scenarios, the failure data comprising, for each failure scenario, at least one segment; and identifying needed capacities for the backbone network by: determining, for each time period in the demand data and supply data, a needed capacity for each of the cables in the backbone network by: assigning, for each of the failure scenarios in the failure data, a network flow to each of the cables based on the failure scenario, wherein the network flow assigned to each cable is less than or equal to the available capacity for that cable for the time period, and wherein the demand for the time period associated with each pair of first and second nodes is satisfied by the assigned flow between the first and second node; and determining, for each cable in the backbone network, a needed capacity for the cable for the time period based on the network flows assigned to the cable for each of the failure scenarios; and generating, based on the needed capacity of each cable in the backbone network for each time period and the upfront cost amount and recurring cost amount associated with each cable, a capacity provisioning plan comprised of a provisioned capacity for each cable at each time period. ### Claim 20 (depends on 19) The computer-readable storage medium of claim 19 wherein determining the provisioned capacity for each cable in the backbone network for each time period comprises optimizing how much capacity is provisioned from each cable at each time period to minimize a total of costs associated with all cables, wherein the cost associated with a cable is based on (1) the upfront cost amount for the cable and (2) the recurring cost amount for the cable and the number of time periods during which capacity is provisioned from that cable, and wherein minimizing the total of costs associated with all cables is modeled as a multi-commodity flow problem.