The Yelf Spiral

Educators, corporate executives, and everyday computer users probably agree that the Internet has made it easier and faster to complete projects. However; as technology evolves, so does the demand from a fickle consuming public. We want better, faster, smaller products.

ASU researchers are helping with the “better” and “faster” parts. They’ve developed a technique that helps reduce the inconsistency of waiting time that Internet users experience when working online.

As is the case with many other inventions, there is always room for improvement, says Nong Ye, director of ASU’s Information & Systems Assurance Laboratory (ISAL). Ye and ASU colleagues Xueping Li and Toni Farley created what they call the Yelf Spiral. Named for its three researcher/inventors (Ye, Li and Farley), the Yelf Spiral is a technique for determining the order of jobs to be serviced on-line.

It works to reduce the inconsistency of waiting time. Ye says that the technique involves scheduling jobs in a spiral fashion based on their processing times.

“This technique has commercial applications in any situation where jobs require scheduling, and where reducing the variance in job waiting time would prove beneficial,”

Ye explains. “Such applications exist in almost all fields, including computers, cabled or wireless computer networks, Internet, electric power networks, transportation networks, and others.”

Think about the process of scheduling requests (jobs) in a Web server, she adds. By reducing the variance of Web request waiting times, user expectations can more easily be established and met. Many situations already exist where a set of jobs must be scheduled to run on one resource.

For example, a Web server often needs to schedule multiple requests for processing. Minimizing the variance in wait time before jobs are serviced may provide stability and predictability to a system. Farley says that the Yelf Spiral can improve the quality of service provided to Internet users.

“People don’t like uncertainty in waiting,” she says. “Our technique allows people an option. They can decide how long they want to wait, or if they want to wait at all. It allows them to use their time more efficiently. It also gives them a better sense of assurance with regard to their job completion.”

“By minimizing waiting time variance, we can set tighter bounds (predictability) on waiting time for providing Quality of Service (QoS) to the user,” Ye adds. “The Yelf Spiral is a job ordering method.”

How does it work? Consider a set of jobs with processing times 1, 2, 3, 4, 5, 6, and 7. The smallest job has the shortest processing time. The largest job has the longest processing time. The Yelf Spiral orders the jobs to reduce waiting time. The process is as follows:

Find smallest job and place in middle of sequence list.
Find largest job and place at end of list.
Find second largest job and place at beginning of list.
Find third largest job and place before largest job.
Find fourth largest job and place before third largest job.
Find next largest job and place before or after smallest job, depending on which placement produces smaller variance of waiting times for jobs in current list.
Repeat Step 6 for the remaining jobs.

Using the example, the jobs will be ordered as follows: 6, 3, 2, 1, 4, 5, 7.

The technique can be thought of as a spiral due to the nature of the ordering method. The point of the spiral begins from the outer edge of the list at the end and proceeds to the inside of the list.

“We’ve performed extensive testing of the Yelf Spiral method in comparison with many existing, popular scheduling methods,” Ye says. “The Yelf Spiral has always produced the minimum variance of job waiting times. It’s really something that all Internet users could benefit from using.”—Manny Romero