Kao M.-Y. (ed.) Encyclopedia of Algorithms

Подождите немного. Документ загружается.

798 R Routing in Road Networks with Transit Nodes

Routing in Road Networks with Transit Nodes, Table 1

Statistics on preprocessing. The size of transit-node sets, the number of entries in distance tables, and the average number of access

nodes to the respective layer are given; furthermore, the space overhead and the preprocessing time

layer 1 layer 2 layer 3

jT j |A|avg. jT

j |table

|[10

] |A

|avg. jT

j |table

|[10

] space [B/node] time [h]

Europe 11 293 9.9 323 356 130 4.1 2 954 721 119 251 2:44

USA 10 674 5.7 485 410 204 4.2 3 855 407 173 244 3:25

Routing in Road Networks with Transit Nodes, Table 2

Performance of transit-node routing with respect to 10 000 000 random queries. The column for layer i specifies which fraction of the

queries is correctly answered using only information available at layers  i. Each box spreads from the lower to the upper quartile

and contains the median, the whiskers extend to the minimum and maximum value omitting outliers, which are plotted individ ually

#nodes #edges layer 1 layer 2 layer 3 query

Europe 18 029 721 42 199 587 99.74% 99.9984% 99.99981% 5.6 s

USA 24 278 285 58 213 192 99.89% 99.9986% 99.99986% 4.9 s

Routing in Road Networks with Transit Nodes, Figure 2

Query time distribution as a function of Dijkstra rank–the number of iterations Dijkstra’s algorithm would need to solve this instance.

The d istributions are represented as box-and-whisker plots: each box spreads from the lower to the upper quartile and contains the

median, the whiskers extended to the minimum and maximum value omitting, which are plotted individually

There are two diﬀerent implementations: one is based

on a simple geometric grid and one on highway hierar-

chies, the fastest previous approach [5,6]. A highway hier-

archy consists of a sequence of levels (Fig. 1), where level

i + 1 is constructed from level i by bypassing low-degree

nodes and removing edgesthat never appear far away from

the source or target of a shortest path. Interestingly, these

levels are geometrically decreasing in size and otherwise

Routing in Road Networks with Transit Nodes R 799

similar to each other. The highest level contains the most

‘important’ nodes and becomes the primary transit-node

set. The nodes of lower levels are used to form the transit-

node sets of subordinated layers.

Applications

Apart from the most obvious applications in car navi-

gation systems and server-based route planning systems,

transit-node routing can be applied to several other ﬁelds,

for instance to massive traﬃc simulations and to various

optimization problems in logistics.

Open Problems

It is an open question whether one can ﬁnd better transit-

node sets or a better locality ﬁlter so that the performance

can be further improved. It is also not clear if transit-node

routing can be successfully applied to other graph types

than road networks. In this context, it would be desir-

able to derive some theoretical guarantees that apply to

any graph that fulﬁlls certain properties. For some practi-

cal applications, a dynamic version of transit-node routing

would be required in order to deal with time-dependent

networks or unexpected edge weight changes caused, for

example, by traﬃc jams. The latter scenario can be handled

by a related approach [8], which is, however, considerably

slower than transit-node routing.

Experimental Resul t s

Experiments were performed on road networks of West-

ern Europe and the USA using a cost function that solely

takes expected travel time into account. The results exhibit

various tradeoﬀs between average query time (5 μs to 63 μs

for the USA), preprocessing time (59 min to 1200 min),

and storage overhead (21 bytes/node to 244 bytes/node).

For the variant that uses three layers and is tuned for best

query times, Tables 1 and 2 show statistics on the prepro-

cessing and the query performance, respectively. The av-

erage query times of about 5 μs are six orders of magni-

tude faster than Dijkstra’s algorithm. In addition, Fig. 2

gives for each rank r on the x-axis a distribution for 1 000

queries with random starting point s and the target node t

for which Dijkstra’s algorithm would need r iterations to

ﬁnd it. The three layers of transit-node routing with small

transition zones in between can be recognized: for large

ranks, it is suﬃcient to access only the primary layer yield-

ing query times of about 5 μs, for smaller ranks, additional

layers have to be accessed resulting in median query times

of up to 20 μs.

Data Sets

The European road network has been provided by the

company PTV AG, the US network has been obtained

from the TIGER/Line Files [9]. Both graphs have also been

used in the 9th DIMACS Implementation Challenge on

Shortest Paths [1].

URL to Code

The source code might be published at some point in the

future at http://algo2.iti.uka.de/schultes/hwy/.

Cross References

 All Pairs Shortest Paths in Sparse Graphs

 All Pairs Shortest Paths via Matrix Multiplication

 Decremental All-Pairs Shortest Paths

 Engineering Algorithms for Large Network

Applications

 Fully Dynamic All Pairs Shortest Paths

 Geographic Routing

 Implementation Challenge for Shortest Paths

 Shortest Paths Approaches for Timetable Information

 Shortest Paths in Planar Graphs with Negative Weight

Edges

 Single-Source Shortest Paths

Recommended Reading

1. 9th DIMACS Implementation Challenge: Shortest Paths. http://

www.dis.uniroma1.it/~challenge9/ (2006)

2. Bast,H.,Funke,S.,Matijevic,D.,Sanders,P.,Schultes,D.:Intran-

sit to constant time shortest-path queries in road networks. In:

Workshop on Algorithm Engineering and Experiments, 2007,

pp. 46–59

3. Bast, H., Funke, S., Sanders, P., Schultes, D.: Fast routing in road

networks with transit nodes. Science 316(5824), 566 (2007)

4. Dijkstra, E.W.: A note on two problems in connexion with

graphs.Numer.Math.1 269–271 (1959)

5. Sanders, P., Schultes, D.: Highway hierarchies hasten exact

shortest path queries. In: 13th European Symposium on Algo-

rithms. LNCS, vol. 3669, pp. 568–579. Springer, Berlin (2005)

6. Sanders, P., Schultes, D.: Engineering highway hierarchies. In:

14th European Symposium on Algorithms. LNCS, vol. 4168,

pp. 804–816. Springer, Berlin (2006)

7. Sanders, P., Schultes, D.: Engineering fast route planning algo-

rithms. In: 6th Workshop on Experimental Algorithms. LNCS,

vol. 4525, pp. 23–36. Springer, Berlin (2007)

8. Schultes, D., Sanders, P.: Dynamic highway-node routing. In:

6th Workshop on Experimental Algorithms. LNCS, vol. 4525,

pp. 66–79. Springer, Berlin (2007)

9. U.S. Census Bureau, Washington, DC: UA Census 2000

TIGER/Line Files. http://www.census.gov/geo/www/tiger/

tigerua/ua_tgr2k.html (2002)

800 R R-Trees

R-Trees

2004; Arge, de Berg, Haverkort, Yi

KE YI

Hong Kong University of Science and Technology,

Hong Kong, China

Keywords and Synonyms

R-Trees; Spatial databases; External memory data struc-

tures

Problem Definition

Problem Statement and the I/O Model

Let S be a set of N axis-parallel hypercubes in R

. A very

basic operation in a spatial database is to answer window

queries on the set S.AwindowqueryQ is also an axis-

parallel hypercube in R

that asks us to return all hyper-

cubes in S that intersect Q.SincethesetS is typically huge

in a large spatial database, the goal is to design a disk-based,

or external memory data structure (often called an index

in the database literature) such that these window queries

can be answered eﬃciently. In addition, given S,thedata

structure should be constructed eﬃciently, and should be

able to support insertions and deletions of objects.

When external memory data structures are concerned,

the standard external memory model [2], a.k.a. the I/O

model, is often used as the model of computation. In this

model, the machine consists of an inﬁnite-size external

memory (disk) and a main memory of size M.Ablockof

B consecutive elements can be transferred between main

memory and disk in one I/O operation (or simply I/O). An

external memory data structure is a structure that is stored

on disk in blocks, but computation can only occur on ele-

mentsinmainmemory,soanyoperation(e.g.query,up-

date, and construction) on the data structure must be per-

formed using a number I/Os, which is the measure for the

complexity of the operation.

R-Trees

The R-tree, ﬁrst proposed by Guttman [9], is a multi-way

tree

T , very similar to a B-tree, that is used to store the set

S such that a window query can be answered eﬃciently.

Each node of

T ﬁts in one disk block. The hypercubes of

S are stored only in the leaves of

T . All leaves of T are

on the same level, and each stores (B)hypercubesfrom

S; while each internal node, except the root, has a fan-out

of (B). The root of

T may have a fan-out as small as 2.

For any node u 2

T,letR(u) be the smallest axis-parallel

hypercube, called the minimal bounding box,thatencloses

all the hypercubes stored below u. At each internal node

v 2

T , whose children are denoted v

,:::,v

,thebound-

ing box R(v

) is stored along with the pointer to v

for

i =1;:::;k. Note that these bounding boxes may overlap.

Please see Fig. 1 for an example of an R-tree in two dimen-

sions.

For a window query Q, the query answering process

starts from the root of

T and visits all nodes u for which

R(u)intersectsQ.Whenreachingaleafv,itcheckseach

hypercube stored at v to decide if it should be reported.

The correctness of the algorithm is obvious, and the eﬃ-

ciency (the number of I/Os) is determined by the number

of nodes visited.

Any R-tree occupies a linear number O(N/B)disk

blocks, but diﬀerent R-trees might have diﬀerent query,

update, and construction costs. When analyzing the query

complexity of window queries, the output size T is also

used, in addition to N, M,andB.

Key Results

Although the structure of an R-tree is restricted, there is

much freedom in grouping the hypercubes into leaves and

grouping subtrees into bigger subtrees. Diﬀerent group-

ing strategies result in diﬀerent variants of R-trees. Most

oftheexistingR-treesusevarious heuristics to group to-

gether hypercubes that are “close” spatially, so that a win-

dow query will not visit too many unnecessary nodes. Gen-

erally speaking, there are two ways to build an R-tree: re-

peated insertion and bulk-loading. The former type of al-

gorithms include the original R-tree [9], the R

-tree [15],

the R*-tree [6], etc. These algorithms use O(log

N)I/Os

to insert an object and hence O(N log

N)I/Ostobuild

theR-treeonS, which is not scalable for large N.When

the set S isknowninadvance,itismuchmoreeﬃcientto

bulk-load the entire R-tree at once. Many bulk-loading al-

gorithms have been proposed, e. g. [7,8,10,11,13]. Most of

thesealgorithmsbuildtheR-treewithO(N/B log

M/B

N/B)

I/Os (the number of I/Os needed to sort N elements), and

they typically result in better R-trees than those obtained

by repeated insertion. During the past decades, there have

been a large number of works devoted to R-trees from the

database community, and the list here is by no means com-

plete. The reader is referred to the book by Manolopou-

los et al. [14] for an excellent survey on this subject in the

database literature. However, no R-tree variant mentioned

above has a guarantee on the query complexity; in fact,

Arge et al. [3] constructed an example showing that some

of the most popular R-trees may have to visit all the nodes

without reporting a single result.

R-Trees R 801

R-Trees, Figure 1

An R-tree example in two dimensions

Fromthetheoreticalperspective,thefollowingarethe

two main results concerning the worst-case query com-

plexity of R-trees.

Theorem 1 ([1,12]) There is a set of N points in R

,such

that for any R-tree

T built on these points, there exists an

empty window query for which the query algorithm has to

visit ˝((N/B)

11/d

) nodes of T .

The priority R-tree, proposed by Arge et al. [3], matches

the above lower bound.

Theorem 2 ([3]) For any set S of N axis-parallel hyper-

cubes in R

, the priority R-tree answers a window query

with O((N/B)

11/d

+ T/B) I/Os. It can be constructed with

O(N/B log

M/B

N/B) I/Os.

It is also reported that the priority R-tree performs well in

practice, too [3]. However, it is not known how to update it

eﬃciently while preserving the worst-case bound. The log-

arithmic method was used to support insertions and dele-

tions [3] but the resulted structure is no longer an R-tree.

Note that the lower bound in Theorem 1 only holds

for R-trees. If the data structure is not restricted to R-trees,

better query bounds can be obtained for the window-query

problem; see e. g. [4].

Applications

R-trees have been used widely in practice due to its sim-

plicity, the ability to store spatial objects of various shapes,

and to answer various queries. The areas of applica-

tions span from geographical information systems (GIS),

computer-aided design, computer vision, and robotics.

When the objects are not axis-parallel hypercubes, they

are often approximated by their minimal bounding boxes,

and the R-tree is then built on these bounding boxes. To

answer a window query, ﬁrst the R-tree is used to locate

all the intersecting bounding boxes, followed by a ﬁlter-

ing step that checks the objects exactly. The R-tree can

also be used to support other kinds of queries, for exam-

ple aggregation queries, nearest-neighbors, etc. In aggre-

gation queries, each object o in S is associated with a weight

w(o) 2 R, and the goal is to compute

w(o)wherethe

sum is taken over all objects that intersect the query range

Q. The query algorithm is same as before, except that in

addition it keeps running sum while traversing the R-tree,

and may skip an entire subtree rooted at some u if R(u)

is completely contained in Q. To ﬁnd the nearest neigh-

bor of a query point q, a priority queue is maintained,

which stores all the nodes u that might contain an object

that is closer to the current nearest neighbor found so far.

The priority of u in the queue is the distance between q

and R(u). The search terminates when the current near-

est neighbor is closer than the top element in the priority

queue. However, no worst-case guarantees are known for

R-trees answering these other types of queries, although

they tend to perform well in practice.

Open Problems

Several interesting problems remain open with respect to

R-trees. Some of them are listed here.

 Is it possible to design an R-tree with the optimal query

bound O((N/B)

11/d

+ T/B) that can also be eﬃciently

updated? Or prove a lower bound on the update cost

for such an R-tree.

 Is there an R-tree that supports aggregation queries for

axis-parallel hypercubes in O((N/B)

11/d

)I/Os?This

would be optimal because the lower bound of Theo-

rem 1 also holds for aggregation queries on R-trees.

Note that, however, no sub-linear worst-case bound ex-

ists for nearest-neighbor queries, since it is not diﬃcult

to design a worst-case example for which the distance

802 R Runs

between the query point q and any bounding box is

smaller than the distance between q and its true nearest

neighbor.

 When the window query Q shrinks to a point, that

is, the query asks for all hypercubes in S that con-

tain the query point, the problem is often referred

to as stabbing queries or point enclosure queries.The

lower bound of Theorem 1 does not hold for this spe-

cial case; while a lower bound of ˝(log

N + T/B)was

proved in [5], which holds in the strong indexability

model. It is intriguing to ﬁnd out the true complex-

ity for stabbing queries using R-trees, which is between

˝(log

N + T/B)andO((N/B)

11/d

+ T/B).

Experimental Results

Nearly all studies on R-trees include experimental evalu-

ations, mostly in two dimensions. Reportedly the Hilbert

R-tree [10,11] has been shown to have good query perfor-

mance while being easy to construct. The R*-tree’s inser-

tion algorithm [6] has often been used for updating the R-

tree. Please refer to the book by Manolopoulos et al. [14]

for more discussions on the practical performance of R-

trees.

Data Sets

Besides some synthetic data sets, the TIGER/Line

data (http://www.census.gov/geo/www/tiger/)fromthe

US Census Bureau has been frequently used as real-

world data to test R-trees. The R-tree portal (http://www.

rtreeportal.org/) also contains many interesting data sets.

URL to Code

Code for many R-tree variants is available at the R-tree

portal (http://www.rtreeportal.org/).Thecodeforthepri-

ority R-tree is available at http://www.cse.ust.hk/~yike/

prtree/.

Cross References

 B-trees

 External Sorting and Permuting

 I/O-model

Recommended Reading

1. Agarwal, P.K., de Berg, M., Gudmundsson, J., Hammar, M.,

Haverkort, H.J.: Box-trees and R-trees with near-optimal query

time. Discret. Comput. Geom. 28, 291–312 (2002)

2. Aggarwal, A., Vitter, J.S.: The input/output complexity of sort-

ing and related problems. In: Communications of the ACM,

vol. 31, pp. 1116–1127 (1988)

3. Arge, L., de Berg, M., Haverkort, H.J., Yi, K.: The priority R-tree:

A practically efficient and worst-case optimal R-tree. In: Proc.

SIGMOD International Conference on Management of Data,

2004, pp. 347–358

4. Arge, L., Samoladas, V., Vitter, J.S.: On two-dimensional index-

ability and optimal range search indexing. In: Proc. ACM Sym-

posium on Principles of Database Systems, 1999, pp. 346–357

5. Arge, L., Samoladas, V., Yi, K.: Optimal external memory planar

point enclosure. In: Proc. European Symposium on Algorithms,

2004

6. Beckmann, N., Kriegel, H.-P., Schneider, R., Seeger, B.: The R*-

tree: An efficient and robust access method for points and rect-

angles. In: Proc. SIGMOD International Conference on Manage-

ment of Data, 1990, pp. 322–331

7. DeWitt, D.J., Kabra, N., Luo, J., Patel, J.M., Yu, J.-B.: Client-server

paradise. In: Proc. International Conference on Very Large

Databases, 1994, pp. 558–569

8. García, Y.J., López, M.A., Leutenegger, S.T.: A greedy algorithm

for bulk loading R-trees. In: Proc. 6th ACM Symposium on Ad-

vances in GIS, 1998, pp. 163–164

9. Guttman, A.: R-trees: A dynamic index structure for spatial

searching. In: Proc. SIGMOD International Conference on Man-

agement of Data, 1984, pp. 47–57

10. Kamel, I., Faloutsos, C.: On packing R-trees. In: Proc. Interna-

tional Conference on Information and Knowledge Manage-

ment, 1993, pp. 490–499

11. Kamel, I., Faloutsos, C.: Hilbert R-tree: An improved R-tree us-

ing fractals. In: Proc. International Conference on Very Large

Databases, 1994, pp. 500–509

12. Kanth, K.V.R., Singh, A.K.: Optimal dynamic range searching in

non-replicatingindex structures. In: Proc. International Confer-

ence on Database Theory. LNCS, vol. 1540, pp. 257–276 (1999)

13. Leutenegger, S.T., Lopez, M.A., Edington, J.: STR: A simple and

efficient algorithm for R-tree packing. In: Proc. 13th IEEE Inter-

national Conference on Data Engineering, 1997, pp. 497–506

14. Manolopoulos, Y., Nanopoulos, A., Papadopoulos, A.N.,

Theodoridis, Y.: R-trees: Theory and Applications. Springer,

London (2005)

15. Sellis, T., Roussopoulos, N., Faloutsos, C.: The R

-tree: A dy-

namic index for multi-dimensional objects. In: Proc. Interna-

tional Conference on Very Large Databases, 1987, pp. 507–518

Runs

 Squares and Repetitions

Schedulers for Optimistic Rate Based Flow Control S 803

Schedulers for Optimistic Rate Based

Flow Control

2005; Fatourou, Mavronicolas, Spirakis

PANAGIOTA FATOUROU

Department of Computer Science,

University of Ioannina, Ioannina, Greece

Keywords and Synonyms

Rate allocation; Rate adjustment; Bandwidth alloca-

tion

Problem Definition

The problem concerns the design of eﬃcient rate-based

ﬂow control algorithms for virtual-circuit communication

networks where a connection is established by allocating

a ﬁxed path, called session, between the source and the des-

tination. Rate-based ﬂow-control algorithms repeatedly

adjust the transmission rates of diﬀerent sessions in an

end-to-end manner with primary objectives to optimize

the network utilization and achieve some kind of fairness

in sharing bandwidth between diﬀerent sessions.

A widely-accepted fairness criterion for ﬂow-control is

max-min fairness which requires that the rate of a session

can be increased only if this increase does not cause a de-

crease to any other session with smaller or equal rate. Once

max-min fairness has been achieved, no session rate can

be increased any further without violating the above con-

dition or exceeding the bandwidth capacity of some link.

Call max-min rates the session rates when max-min fair-

ness has been reached.

Rate-based ﬂow control algorithms perform rate ad-

justments through a sequence of operations in a way that

the capacities of network links are never exceeded. Some

of these algorithms, called conservative [3,6,10,11,12], em-

ploy operations that gradually increase session rates until

they converge to the max-min rates without ever perform-

ing any rate decreases. On the other hand, optimistic algo-

rithms, introduced more recently by Afek, Mansour, and

Ostfeld [1], allow for decreases, so that a session’s rate may

be intermediately be larger than its ﬁnal max-min rate.

Optimistic algorithms [1,7]employaspeciﬁcratead-

justment operation, called update operation (introduced

in [1]). The goal of an update operation is to achieve

fairness among a set of neighboring sessions and optimize

the network utilization in a local basis. More speciﬁcally,

an update operation calculates an increase for the rate

of a particular session (the updated session) for each link

the session traverses. The calculated increase on a partic-

ular link is the maximum possible that respects the max-

min fairness condition between the sessions traversing the

link; that is, this increase should not cause a decrease to the

rate of any other session traversing the link with smaller

rate than the rate of the updated session after the increase.

Once the maximum increase on each link has been cal-

culated the minimum among them is applied to the ses-

sion’s rate (let e be the link for which the minimum in-

crease has been calculated). This causes the decrease of

the rates of those sessions traversing e which had larger

rates than the increased rate of the updated session to

the new rate. Moreover, the update operation guaran-

tees that all the capacity of link e is allocated to the ses-

sionstraversingit(sothebandwidthofthislinkisfully

utilized).

One important performance parameter of a rate-based

ﬂow control algorithm is its locality which is character-

ized by the amount of knowledge the algorithm requires

to decide which session’s rate to update next. Oblivious

algorithms do not assume any knowledge of the network

topology or the current session rates. Partially oblivious al-

gorithms have access to session rates but they are unaware

of the network topology, while non-oblivious algorithms

require full knowledge of both the network topology and

the session rates. Another crucial performance parameter

of rate-based ﬂow control algorithms is the convergence

complexity measured as the maximum number of rate-

804 S Schedulers for Optimistic Rate Based Flow Control

adjustment operations performed in any execution until

max-min fairness is achieved.

Key Results

Fatourou, Mavronicolas and Spirakis [7] have studied the

convergence complexity of optimistic rate-based ﬂow con-

trol algorithms under varying degrees of locality. More

speciﬁcally, they have proved lower and upper bounds

on the convergence complexity of oblivious, partially-

oblivious and non-oblivious algorithms. These bounds are

expressed in terms of n the number of sessions laid out on

the network.

Theorem 1 (Lower Bound for Oblivious Algorithms, Fa-

tourou, Mavronicolas and Spirakis [7]) Any optimistic,

oblivious, rate-based ﬂow control algorithm requires ˝(n

)

update operations to compute the max-min rates.

Fatourou, Mavronicolas and Spirakis [7]havepresented

algorithm RoundRobin, which applies update oper-

ations to sessions in a round robin order. Obviously,

RoundRobin is oblivious. It has been proved [7] that the

convergence complexity of RoundRobin is O(n

). This

shows that the lower bound for oblivious algorithms is

tight.

Theorem2(UpperBoundforObliviousAlgorithms,Fa-

tourou, Mavronicolas and Spirakis [7]) RoundRobin

computes the max-min rates after performing O(n

)

update operations.

RoundRobin belongstoaclassofobliviousalgorithms,

called Epoch [7]. Each algorithm of this class repeatedly

chooses some permutation of all session indices and ap-

plies update operations on the sessions in the order de-

termined by this permutation. This is performed n times.

Clearly, Epoch is a class of oblivious algorithms. It has

been proved [7] that each of the algorithms in this class

has convergence complexity O(n

Another oblivious algorithm, called Arbitrary,has

been presented in [1]. The algorithm works in a very sim-

ple way by choosing the next session to be updated in an

arbitrary way, but it requires an exponential number of

update operations to compute the max-min rates.

Fatourou, Mavronicolas and Spirakis [7] have proved

that partially-oblivious algorithms do not achieve better

convergence complexity than oblivious algorithms despite

the knowledge they employ.

Theorem 3 (Lower Bound for Partially Oblivious Algo-

rithms, Fatourou, Mavronicolas and Spirakis [7]) Any

optimistic, partially oblivious, rate-based ﬂow control algo-

rithm requires ˝(n

) update operations to compute the

max-min rates.

Afek, Mansour and Ostfeld [1] have presented a partially

oblivious algorithm, called GlobalMin.Thealgorithm

chooses as the session to update next the one with the min-

imum rate among all sessions. The convergence complex-

ity of GlobalMin is O(n

)[1]. This shows that the lower

bound for partially-oblivious algorithms is tight.

Theorem 4 (Upper Bound for Partially Oblivious algo-

rithms, Afek, Mansour and Ostfeld [1]) GlobalMin

computes the max-min rates after performing O(n

)

update operations.

Another partially-oblivious algorithm, called LocalMin,

is also presented in [1]. The algorithm chooses to sched-

ule next a session which has a minimum rate among all

the sessions that share a link with it. LocalMin has time

complexity O(n

Fatourou, Mavronicolas and Spirakis [7]havepre-

sented a non-oblivious algorithm, called Linear,thatex-

hibits linear convergence complexity. Linear follows the

classical idea [3,12] of selecting as the next updated session

one of the sessions that traverse the most congested link in

the network. To discover such a session, Linear requires

knowledge of the network topology and the session rates.

Theorem 5 (Upper Bound for Non-Oblivious Al-

gorithms, Fatourou, Mavronicolas and Spirakis [7])

Linear computes the max-min rates after performing

O(n) update operations.

The convergence complexity of Linear is optimal, since

n rate adjustments must be performed in any execution of

an optimistic rate-based ﬂow control algorithm (assuming

that the initial session rates are zero). However, this comes

at a remarkable cost in locality which makes Linear

impractical.

Applications

Flow control is the dominant technique used in most

communication networks for preventing data traﬃc con-

gestion when the externally injected transmission load

is larger than what can be handled even with optimal

routing. Flow control is also used to ensure high net-

work utilization and fairness among the diﬀerent connec-

tions. Examples of networking technologies where ﬂow

control techniques have been extensively employed to

achieve these goals are TCP streams [5]andATMnet-

works [4]. An overview of ﬂow control in practice is pro-

vided in [3].

Schedulers for Optimistic Rate Based Flow Control S 805

Theideaofcontrollingtherateofatraﬃcsourceorig-

inates back to the data networking protocols of the ANSI

Frame Relay Standard. Rate-based ﬂow control is consid-

ered attractive due to its simplicity and its low hardware

requirements. It has been chosen by the ATM Forum on

Traﬃc Management as the best suited technique for the

goals of ABR service [4].

A substantial amount of research work has been

devoted in past to conservative ﬂow control algo-

rithms [3,6,10,11,12]. The optimistic framework has been

introduced much later by Afek et al. [1]asamoresuit-

able approach for real dynamic networks where decreases

of session rates may be necessary (e. g., for accommo-

dating the arrival of new sessions). The algorithms pre-

sented in [7] improve upon the original algorithms pro-

posed in [1] in terms of either convergence complexity, or

locality, or both. Moreover, they identify that certain clas-

sical scheduling techniques, such as round-robin [11], or

adjusting the rates of sessions traversing one of the most

congested links [3,12] can be eﬃcient under the optimistic

framework. The ﬁrst general lower bounds on the conver-

gence complexity of rate-based ﬂow control algorithms are

also presented in [7].

The performance of optimistic algorithms has been

theoretically analyzed in terms of an abstraction, namely

the update operation, which has been designed to ad-

dress most of the intricacies encountered by rate-based

ﬂow control algorithms. However, the update operation

masks low-level implementation details,while it may incur

non-trivial, local computations on the switches of the net-

work. Fatourou, Mavronicolas and Spirakis [9]havestud-

ied the impact on the eﬃciency of optimistic algorithms

of local computations required at network switches in or-

der to implement the update operation, and proposed

a distributed scheme that implements a broad class of such

algorithms. On a diﬀerent avenue, Afek, Mansour and

Ostfeld [2] have proposed a simple ﬂow control scheme,

called Phantom, which employs the idea of considering

an imaginary session on each link [10,12], and they have

discussed how Phantom can be applied to ATM networks

and networks of TCP routers.

A broad class of modern distributed applications (e. g.,

remote video, multimedia conferencing, data visualiza-

tion, virtual reality, etc.) exhibit highly diﬀering band-

width requirements and need some kind of quality of ser-

vice guarantees. To eﬃciently support a wide diversity of

applications sharing available bandwidth, a lot of research

work has been devoted on incorporating priority schemes

on current networking technologies. Priorities oﬀer a basis

for modeling the diverse resource requirements of mod-

ern distributed applications, and they have been used to

accommodate the needs of network management policies,

traﬃc levels, or pricing. The ﬁrst eﬀorts for embedding

priority issues into max-min fair, rate-based ﬂow control

were performed in [10,12]. An extension of the classical

theory of max-min fair, rate-based ﬂow control to accom-

modate priorities of diﬀerent sessions has been presented

in [8]. (A number of other papers addressing similar gen-

eralizations of max-min fairness to account for priorities

and utility have been presented after the original publica-

tion of [8].)

Many modern applications are not based solely on

point-to-point communication but they rather require

multipoint-to-multipoint transmissions. A max-min fair

rate-based ﬂow control algorithm for multicast networks

is presented in [14]. Max-min fair allocation of bandwidth

in wireless adhoc networks is studied in [15].

Open Problems

The research work on optimistic, rate-based ﬂow control

algorithms leaves open several interesting questions. The

convergence complexity of the proposed optimistic algo-

rithms has been analyzed only for a static set of sessions

laid out on the network. It would be interesting to evalu-

ate these algorithms under a dynamic network setting, and

possibly extend the techniques they employ to eﬃciently

accommodate arriving and departing sessions.

Although max-min fairness has emerged as the most

frequently praised fairness criterion for ﬂow control al-

gorithms, achieving it might be expensive in highly dy-

namic situations. Afek et al. [1]haveproposedamodi-

ﬁed version of the update operation, called approximate

update, which applies an increase to some session only if

it is larger than some quantity ı>0. An approximate opti-

mistic algorithm uses the approximate update operation

and terminates if no session rate can be increased by more

than ı. Obviously such an algorithm does not necessar-

ily reach max-min fairness. It has been proved [1]thatfor

some network topologies every approximate optimistic al-

gorithm may converge to session rates that are away from

their max-min counterparts by an exponential factor. The

consideration of other versions of update operation or

diﬀerent termination conditions might lead to better max-

min fairness approximations and deserves more study; dif-

ferent choices may also signiﬁcantly impact the conver-

gence complexity of approximate optimistic algorithms.

It would be also interesting to derive trade-oﬀ results be-

tween the convergence complexity of such algorithms and

the distance of the terminating rates they achieve to the

max-min rates.

806 S Scheduling with Equipartition

Fairness formulations that naturally approximate the

max-min condition have been proposed by Kleinberg et

al. [13] as suitable fairness criteria for certain routing and

load balancing applications. Studying these formulations

under the rate-based ﬂow control setting is an interesting

open problem.

Cross References

 Multicommodity Flow, Well-linked Terminals and

Routing Problems

Recommended Reading

1. Afek, Y., Mansour, Y., Ostfeld, Z.: Convergence complexity of

optimistic rate based flow control algorithms. J. Algorithms

30(1), 106–143 (1999)

2. Afek, Y., Mansour, Y., Ostfeld, Z.: Phantom: a simple and effec-

tive flow control scheme. Comput. Netw. 32(3), 277–305 (2000)

3. Bertsekas, D.P., Gallager, R.G.: Data Networks, 2nd edn. Pren-

tice Hall, Englewood Cliffs (1992)

4. Bonomi, F., Fendick, K.: The Rate-Based Flow Control for Avail-

able Bit Rate ATM Service. IEEE/ACM Trans. Netw. 9(2), 25–39

(1995)

5. Brakmo, L.S., Peterson, L.: TCP Vegas: End-to-end Congestion

Avoidance on a Global Internet. IEEE J. Sel. Areas Commun.

13(8), 1465–1480 (1995)

6. Charny, A.: An algorithm for rate-allocation in a packet-

switching network with feedback. Technical Report MIT/LCS/

TR-601, Massachusetts Institute of Technology, April 1994

7. Fatourou, P., Mavronicolas, M., Spirakis, P.: Efficiency of oblivi-

ous versus non-oblivious schedulers for optimistic, rate-based

flow control. SIAM J. Comput. 34(5), 1216–1252 (2005)

8. Fatourou, P., Mavronicolas, M., Spirakis, P.: Max-min fair flow

control sensitive to priorities. J. Interconnect. Netw. 6(2), 85–

114 (2005) (also in Proceedings of the 2nd International Con-

ference on Principles of Distributed Computing, pp. 45–59

(1998)

9. Fatourou, P., Mavronicolas, M., Spirakis, P.: The global effi-

ciency of distributed, rate-based flow control algorithms. In:

Proceedings of the 5th Colloqium on Structural Information

and Communication Complexity, pp. 244–258, June 1998

10. Gafni, E., Bertsekas, D.: Dynamic control of session input

rates in communication networks. IEEE Trans. Autom. Control

29(11), 1009–1016 (1984)

11. Hahne, E.: Round Robin Scheduling for Max-min Fairness in

Data Networks. IEEE J. Sel. Areas Commun. 9(7), 1024–1039

(1991)

12. Jaffe, J.: Bottleneck Flow Control. IEEE Trans. Commun. 29(7),

954–962 (1981)

13. Kleinberg, J., Rabani, Y., Tardos, É.: Fairness in routing and load

balancing. In: Proceedings of the 40th Annual IEEE Symposium

on Foundations of Computer Science, pp. 568–578, October

1999

14. Sarkar, S., Tassiulas, L.: Fair distributed congestion control in

multirate multicast networks. IEEE/ACM Trans. Netw. 13(1),

121–133 (2005)

15. Tassiulas, L., Sarkar, S.: Maxmin fair scheduling in wireless

adhoc networks. IEEE J. Sel. Areas Commun. 23(1), 163–173

(2005)

Scheduling with Equipartition

2000; Edmonds

JEFF EDMONDS

York University, Toronto, ON, Canada

Keywords and Synonyms

Round Robin and Equi-partition are the same algorithm.

Average Response time and Flow are basically the same

measure.

Problem Definition

The task is to schedule a set of n on-line jobs on p pro-

cessors. The jobs are J =

;:::;J

where job J

has a re-

lease/arrival time r

and a sequence of phases hJ

; J

;:::;

i. Each phase is represented by hw

;

i,wherew

de-

notes the amount of work and 

is the speedup function

specifying the rate 

(ˇ) at which this work is executed

when given ˇ processors.

A phase of a job is said to be fully parallelizable

its speedup function is  (ˇ)=ˇ.Itissaidtobesequen-

tial

if its speedup function is  (ˇ)=1.

A speedup

function  is nondecreasing iﬀ  (ˇ

)   (ˇ

) whenever

 ˇ

;

is sublinear iﬀ  (ˇ

)/ˇ

  (ˇ

)/ˇ

;

and

is strictly-sublinear by ˛ iﬀ  (ˇ

)/ (ˇ

) 

(

/ˇ

)

1˛

An s-speed scheduling algorithm S

(J) allocates s  p

processors each point in time to the jobs J in a way such

that all the work completes.

More formally, it constructs

afunction

S(i; t)from

1;:::;n

[0; 1)to[0; sp]giv-

ing the number of processors allocated to job J

at time

t. (A job is allowed to be allocated a non-integral num-

ber of processors.) Requiring that for all t,

i=1

S(i; t) 

sp ensures that at most sp processors are allocated at

any given time. Requiring that for all i,thereexistr

< c

<  < c

such that for all 1  q  q

Note that an odd feature of this deﬁnition is that a sequential job

completes work at a rate of 1 even when absolutely no processors are

allocated to it. This assumption makes things easier for the adversary

and harder for any non-clairvoyant algorithm. Hence, it only makes

these results stronger.

A job phase with a nondecreasing speedup function executes no

slower if it is allocated more processors.

A measure of how eﬃcient a job utilizes its processors is  (ˇ )/ˇ ,

which is the work completed by the job per time unit per proces-

sor. A sublinear speedup function is one whose eﬃciency does not

increase with more processors. This is a reasonable assumption if in

practice ˇ

processors can simulate the execution of ˇ

processors in

afactorofatmostˇ

/ˇ

more time.

(J) is deﬁned to be the scheduler with p processors of speed s.

and S

are equivalent on fully parallelizable jobs and S

is s times

faster than S

on sequential jobs.

Scheduling with Equipartition S 807

q1



(S(i; t))dt = w

ensures that before a phase of

a job begins, the job must have been released and all of

the previous phases of the job must have completed. The

completion time of a job J

, denoted c

,isthecompletion

time of the last phase of the job.

The goal of a scheduling algorithm is to mini-

mize the average response time,

i2J

 r

), of the

jobs or equivalently its ﬂow time S

(J)=

i2J

 r

An alternative formalization is to integrate over time

the number of jobs n

alive at time t, S

(J)=

i2J

is alive a time t)ıt =

ıt.

A scheduling algorithm is said to be on-line if it lacks

knowledge of which jobs will arrive in the future. It is said

to be non-clairvoyant if it also lacks all knowledge about

the jobs that are currently in the system, except for know-

ing when a job arrives and knowing when it completes.

The two examples of non-clairvoyant schedulers that

are often used in practice are Equi-partition (also called

Round Robin)andBalance. EQUI

is deﬁned to be the

scheduler that allocates an equal number of processors to

each job that is currently alive. That is, for all i and t,ifjob

is alive at time t,thenEQUI(i; t)=sp/n

,wheren

thenumberofjobsthatarealiveattimet. The schedule

BAL

is deﬁned in [8] to be the schedule that allocates all

of its processors to the job that has been allocated proces-

sors for the shortest length of time. (Though no one imple-

ments Balance directly, Unix uses a multi-level feedback

(MLF) queue algorithm which in a way approximates Bal-

ance).

The most obvious worst-case measure of the goodness

of an online non-clairvoyant scheduling algorithm S is its

competitive ratio. This compares the perform of the algo-

rithm to that of the optimal scheduler. However, in many

cases, the limited algorithm is unable to compete against

an all knowing all powerful optimal scheduler. To com-

pensate the algorithm S

, it is given extra speed s.Anon-

line scheduling algorithm S is said to be s-speed c-competi-

tive if: max

(J)/Opt(J)  c. For example, being s-speed

2-competitive means that the cost S

(J) of scheduler S with

s  p processors on any instance J is at most twice the op-

timal cost for the same jobs when only given p processors.

Key Results

If all jobs arrive at time zero (batch), then the ﬂow time

of EQUI is 2-competitive on fully parallelizable jobs [10]

and (2 +

3)-competitive on jobs with nondecreasing

sublinear speedup functions [3]. (The time until the last

job completes (makespan) on fully parallelizable jobs is

the same for EQUI and OPT, but can be a factor of

Scheduling with Equipartition, Figure 1

To understand the motivation for this resource augmentation

analysis [8], note that it is common for the quality of service of

a system to have a threshold property with respect to the load

that it is given. In this example, it seems that the online schedul-

ing algorithm S performs reasonably well in comparison to the

optimal scheduling algorithm. Despite this, one can see that the

competitive ratio of S is huge by looking at the vertical gap b e-

tween the curves when the load is near capacity. To explain why

these curves are close, one must also measure the horizontal gap

between curves. S performs at most c times worse than optimal,

when either the load is decreased or equivalently the speed is

increased by factor of s

(log n/loglogn)worseforEQUI if the jobs can also have

sequential phases [11].) Table 1 summarizes all the results.

When the jobs have arbitrary arrival times and are

fully parallelizable, the optimal schedule simply allocates

all the processors to the jobs with least remaining work.

This, however, requires the scheduler to know the amount

of work per job. Without this knowledge, EQUI and BAL

are unable to compete with the optimal and hence can do

afactorof˝(n/logn)and˝(n) respectively worse and no

non-clairvoyant schedulers has a better competitive ratio

than ˝(n

1/3

)[9,10]. Randomness improves the compet-

itive ratio of BAL to (log n log log n)[7]. Having more

(or faster) processors also helps. BAL

achieves a s =1+

speed competitive ratio of

s1

=1+



[8].

If some of the jobs are fully parallelizable and some are

sequential jobs, it is hard to believe that any non-clairvoy-

ant scheduler, even with sp processors, can perform well.

Not knowing which jobs are which, it waists too many

processors on the sequential jobs. Being starved, the fully

parallelizable jobs fall further and further behind and then

other fully parallelizable jobs arrive which fall behind as

well. For example, even the randomized version of BAL