Bandwidth on Demand (BoD) describes a network management problem, where users can request large amounts of bandwidth, but only for some fixed time interval. The network management tool must find out if such a request can be accommodated on the network, and if yes, must provision the network to provide the service at its start-time, and then remove the provisioning at the end of the service period. Parc Technologies and IC-Parc developed such a Bandwidth on Demand solution for Schlumberger in 2003, which was installed on their dexa.net network. I was working on the solver side of this project with Quanshi Xia from IC-Parc, while Nick Bradshaw and Peter Rylance from Parc Technologies worked on the overall system design and implementation. The project was managed by Barry Richards, the director of IC-Parc.
Why is Bandwidth on Demand an important problem for Schlumberger? Schlumberger is one the of largest oil-field services providers in the world. Historically, well logging is at the core of its business, and today the company offers many different sensor packs that can be placed in the drill hole. The picture on the left shows such a sensor tool, which looks like yet another piece of pipe in the drill stack, but contains different types of sensors plus data collection and forwarding equipment, operating in one of the toughest environments imaginable. In modern well logging equipment, a multitude of data (up to 12Mbs is quoted) can be collected while the drilling is ongoing. Some of that data is used directly at the drill site for control of the drilling operation, but much of the data must be analyzed centrally in a data centre. Historically, the logging data (reels of data tape) would be sent by courier to the central office, as the network connection to the well head did not have enough capacity. Delays of several days would ensue. Modern VSAT satellite links and optical fibres along-side pipelines do provide enough capacity to carry this data to the network backbone. In the data centre the data is analyzed and visualized with a multitude of tools. The drilling operation is often controlled by a consortium of companies, all of which must be involved in the decision-making process. As their analysis experts are in very high demand, it is impossible to require physical meetings for these discussions. Instead, video conferencing supported by shared data visualization is used to connect multiple sites around the world. As the cost of drilling operations can be very high, all this IT infrastructure must work as advertised, i.e. faults in data collection, transport and analysis may not delay the drilling. One way of achieving this is by using a specialized, high-performance network.
A Global Enterprise Network
The dexa.net network was designed as a global enterprise network, providing connectivity to places that normal ISPs do not go, like off-shore oil fields, or seismic exploration ships. The “last mile” connectivity very often is by VSAT satellite link, but a global wired network connects centers of oil exploration and data analysis.
The image above shows a diagram of dexa.net from my CP-AI-OR 2004 tutorial. This is an enterprise network, not a carrier network. This means that the connection links are rented from telecoms, and are thus sized carefully based on current and future demands to reduce rental cost. Providing enough spare capacity for an unlimited number of well logging tasks is not economically feasible.
The network infrastructure is based on Cisco 12000 series routers, which offer the required MPLS-TE and DiffServ technologies. MPLS-TE (Traffic Engineering over MPLS (Multi-Protocol Label Switching) provides mechanisms to set up explicit paths between two network nodes, controlling which links are used in the connection. This by-passes the normal routing in the IP network, and gives more flexibility to the network engineer setting up the connection. DiffServ provides multiple traffic classes controlling the queuing in the router interfaces. This allows to favour certain types of traffic over other traffic types, for example making sure that video data is forwarded with (nearly) no packet loss, and low latency and jitter. If too much traffic arrives at some part of the network, other, less important traffic classes are dropped first, while quality of service for the important traffic types is maintained.
The BoD application uses these technologies to set up tunnels for new user demands for the time of their operation. This is an extension of the Demand Acceptance problem, adding a time dimension (fixed start and end) to each demand. Only demands which overlap in time compete for resources, while all demands compete with the normal traffic loads of the network. The tool therefore consists of two main components, a network analysis tool to predict the base load in the network at some future time point, and the routing module which tries to find paths for demands given estimated free capacities.
Note that user demands are not just single point-to-point connections, users typically request a VPN (Virtual Private Network) between multiple locations. This can translate into many point-to-point connections. Finding routes for only some of those binary connections is not enough, the user request will only be satisfied if all connections can be set up at the same time.
The BoD network operates under a first-come, first-serve policy: if a user has made a reservation, which was accepted, then we are no longer allowed to reject the demand at some future time, in order to allow other orders to be satisfied. If the connection has not yet started, we are able to re-route the path, as long as its QoS parameters stay satisfied. If the connection is already live, we are not allowed to touch it, as any modification could lead to loss of connection and unacceptable packet loss. All these constraints mean that we can not solve this problem effectively if we only consider adding point-to-point demands one at a time. We must resolve the complete problem, where some of the previous solution is fixed, and previously accepted demands must be kept. Solving the complete problem for all time points in one step is often not feasible, so that a temporal decomposition must be used.
To learn more
A mathematical description of the Bandwidth on Demand problem is given in chapter 25 of the Handbook of Constraint Programming on Network Applications.