Teaching Complex Systems to Tune Themselves

Story by Al Riske. Photography by Howard Friedenberg.

June 22, 2009 - David Vengerov sees what everyone sees: computer systems are becoming more and more complex every year.

"People are already getting lost in this amount of complexity," he says.

The good news is that network servers can be tuned to do pretty much anything we ask them to do. The bad news? What we want from them tends to change in ways we can't always predict.

"The only thing people can do now to make these systems work well is to set by hand multitudes of different parameters and policies," Vengerov says.

But they can never be sure that those parameters and policies are really the best, because the environment is so often in flux.

A researcher in Sun Labs, Vengerov is part of an emerging consensus that large-scale systems need to be self-managing and self-optimizing.

What sets him apart are his algorithms and his experience in applying them to complex real-world problems.

Vengerov was born in Moscow -- he still speaks with a distinctly Russian accent -- and it was his father who got him interested in complex systems.

"He had been doing the same thing in Russia, but at the much higher level of industry control. Only in Russia could someone be controlling a whole industry, only under central planning," he says. "An industry is such a complex system. You also need to control everything inside of it. How resources are allocated, how trains are moving, supplies -- everything."

His father also believed there were more opportunities in the West, so he brought the family to the United States in 1989. A few years later his son entered the Massachusetts Institute of Technology.

He was telling me even then that this is going to be the problem of the future -- complex systems, modeling and analyzing them, making decisions. Very few people know how to do it. You need a lot of focus and education to learn this. He said. 'Once you learn it, you will be able to apply it everywhere,'" recalls the son. "And that's exactly how it turned out."

At MIT and later Stanford University, Vengerov gained the knowledge he would need to create algorithms that enable systems to observe their constantly changing environments and learn from what they experience.

He started with math, of course, but soon branched out into control theory and reinforcement learning, which have proved invaluable.

Invaluable for dynamic resource allocation. Invaluable for dynamic data migration among storage devices. Invaluable for dynamic user migration in a network of servers. Invaluable for dynamic job scheduling in server farms. Invaluable for dynamic pricing of incoming jobs.

In short, cloud computing.

Reinforcement leaning is easy to understand if you think of how animals learn.

"If they take an action for which they get a positive reinforcement, like a piece of food, they take that action more often. If they get a negative reinforcement, then they try to take that action less often. So animals will gradually change the frequency of their actions towards those that maximize the rewards," Vengerov explains.

With the help of the tuning algorithms he's creating, machines -- and even multi-agent systems -- can learn in the same way.

"Right now people will just heuristically, by hand, specify that we want to drive the system toward this state and not that state. But actually there are an infinite number of states. Reinforcement learning can help establish the value of each state. Then we can take actions," he says.

"For example, now each agent can think, 'Okay, if I give one set of resources to that other agent, how will my state change?' And it can ask another agent, 'How will your state change?' And then they see what is going to be the total value now of the new pair of states. If the total value of the new state will be bigger than the initial value before the exchange, then they figure out this exchange is beneficial and it's good to do it."

Vengerov wants to enable system administrators to work at a much higher level. Instead of concerning themselves with low-level parameters and policies, he says, they should be able to simply choose the kind of performance they want -- could be average response time, could be power efficiency, could be total throughput -- and the system will tune itself for that.

"It's like trial and error but smart. Directed trial and error where you are trying to explore the space of possible actions while at the same time taking the actions that give you the highest reward most often," he says.

"This kind of reinforcement learning algorithm observes statistically the type of request that comes in and then learns to correlate the rewards that it gets with different states and different actions."

The system even learns to generalize based on its previous experience -- a combination of state, action, and reward. That is, similar states and similar actions generally yield similar rewards.

"That allows the system to explore the space of possible states and actions and to take actions that maximize future rewards," Vengerov says.

Earlier theorems and proofs have dealt with single-agent systems, but most of Vengerov's work deals with multi-agent systems.

Consider, for example, dynamic user migration among the servers on a network.

"Here each server is an agent, and they learn how to trade users among themselves so as not to overload any one server, and at the same time place communicating users nearby on the same server so as to reduce the communication time," he says.

"This kind of multi-user framework where agents actually trade different resources, different users -- that's something I haven't seen before."

He hasn't seen it before, but he has shown it, many times.

Vengerov notes that researchers have been trying to apply reinforcement learning to various problems for at least 10 years, but the problems considered so far have been mostly artificial -- and the solutions could not be directly transfered to real-world problems.

"In my work, I have demonstrated how the theory can be applied to several very general and important classes of real-world problems," he says.

"Many design choices need to be made along the way in order to make reinforcement learning fit the problem at hand. I have applied the theory to complex realistic problems many times, so by now I have in my head a plan of steps that need to be taken and 'potholes' that need to be avoided."

So he has been busy demonstrating his results and marketing them to different product groups within Sun.

In fact, he has been collaborating with Solaris engineers on things like thread migration and dynamic bandwidth allocation. He has also worked with Java programmers to embed a self-tuning algorithm in the Java virtual machine -- boosting performance on a well-known benchmark -- SPECjbb2005 -- by 70 percent.

"They said, 'Okay, this we want to include.' It's moving pretty slowly, but they are committed to actually implementing it into Java, so maybe the next JDK will have that algorithm in there," Vengerov says.

Another self-tuning algorithm he created for the Java real-time system has also produced a significant performance boost.

"They have already integrated into the beta release of the next version," he says.

In fact he sees no end to the ways this can be applied. As his father told him years ago:

"Once you learn it, you will be able to apply it everywhere."