Multi-period routing in satellite networks

Research by Raghu Raghavan

Satellite services generate close to $96 billion each year for the telecommunications industry, driven by satellite communications providers that operate large fleets of satellites providing a multitude of services to government agencies and large customers like cable television companies and television networks located all around the globe. Satellites are able to reach even the most remote locations, allowing communication without the need for significant infrastructure investment on the ground. They relay information from location to location for their customers via satellites in geosynchronous orbit at different longitudes. However, the satellites themselves cost hundreds of millions of dollars and have a relatively short lifespan, so companies are under constant pressure to generate as much revenue as possible by using them to the utmost capacity.

In their article “Multi-Period Traffic Routing in Satellite Networks,” S. Raghavan, professor of management science and operations management, and coauthor Ioannis Gamvros, PhD ’06, show how a multi-period routing solution could solve a long-standing problem: how to get the maximum capacity and revenue out of satellite service networks working under rigid time and cost constraints. Raghavan was awarded the 2010 Management Science Strategic Innovation Prize by the European Association of Operational Research Societies at their annual conference in Lisbon, Portugal.

Here is the problem: satellites in geosynchronous orbit are fixed at a certain location in space, remaining always over one spot on the earth. A satellite will have multiple antennae (or beams) to transmit and/or receive telecommunications signals. These beams can communicate with certain regions of the earth that are visible from the satellite’s location; this allows high-definition video, for example, to be transmitted from North America to Europe. Up-beams (toward the satellite) and down-beams (from the satellite towards a specific satellite dish on earth) must be carefully scheduled because not all satellites are capable of carrying the same types of signals, and because there is a limit to the amount of traffic that can be sent and received. If a satellite is close to capacity, there may be no choice but to re-route a customer’s information to another satellite.

That causes a problem for customers. “If you re-route, the customer must reposition their dish, which is a time-consuming process. It takes five to six hours, and there are customers for whom that is not acceptable. You can’t have your cable television network offline for five or six hours,” says Raghavan.

Because most satellite dishes are owned by the customer, service contracts for satellite providers impose hefty penalties if the customer’s dish must be repositioned. In the case of a satellite change the penalty can be as high as 40% of the provider’s fee. In a terrestrial network, rerouting a customer’s traffic does not incur a significant cost. However, for satellite service providers, re-routing carries a serious cost. These costs (or discounts) can significantly affect the revenue generated by customers and are a critical component of the cost structure in the service sector of the satellite industry. As a result decisions concerning which satellite to use initially to route customers or whether to offer the service are extremely important because any deviation from the original commitment entails significant financial losses.

In their paper Raghavan and Gamvros develop an innovative framework to make routing decisions in the present by incorporating information on expected customer demands for many years into the future. Their approach considers routing decisions for customers throughout the entire planning horizon simultaneously, called a multi-period routing approach, instead of progressively. To solve this routing problem the co-authors developed an innovative mathematical technique that applies to a wide range of optimization problems with uncertain information, such as demand information. As a result they were able to generate operational plans for satellite service providers with major cost savings.

Raghavan and Gamvros’s model has been successfully tested on real-world instances with up to 30 satellites, 1,500 services requests, and a planning horizon of five years. In all cases, the model achieved results that were between 40% and 60% better than the satellite company’s previous approach, representing a potential operational cost reduction of about $200 million.

“Multi-Period Traffic Routing in Satellite Networks” is to be published in 2011. For more information about this research, please contact raghavan@umd.edu.