Chicago Journal of Theoretical Computer Science

The MIT Press

Volume 1996, Article 3 31 October 1996

ISSN 1073–0486. MIT Press Journals, 55 Hayward St., Cambridge, MA 02142 USA; (617)253-2889; journals-orders@mit.edu, journals-info@mit.edu. Published one article at a time in L^{A}TEX source form on the Internet. Pagination varies from copy to copy. For more information and other articles see:

• http://www-mitpress.mit.edu/jrnls-catalog/chicago.html

• http://www.cs.uchicago.edu/publications/cjtcs/

• gopher.mit.edu

• gopher.cs.uchicago.edu

• anonymous ftp at mitpress.mit.edu

• anonymous ftp at cs.uchicago.edu Gerstel, Cidon, Zaks Optimal Virtual Path Layout in ATM (Info)

The Chicago Journal of Theoretical Computer Science is abstracted or indexed in Research Alert,◯^{R}SciSearch,◯^{R}Current Contents◯^{R}/Engineering Computing & Technology, and CompuMath Citation Index.◯^{R}

\begin{matrix}c \\ ◯ \end{matrix}1996 The Massachusetts Institute of Technology. Subscribers are licensed to use journal articles in a variety of ways, limited only as required to insure fair attribution to authors and the journal, and to prohibit use in a competing commercial product. See the journal’s World Wide Web site for further details. Address inquiries to the Subsidiary Rights Manager, MIT Press Journals; (617)253-2864; journals-rights@mit.edu.

The Chicago Journal of Theoretical Computer Science is a peer-reviewed scholarly journal in theoretical computer science. The journal is committed to providing a forum for significant results on theoretical aspects of all topics in computer science.

Editor in chief: Janos Simon

Consulting editors: Joseph Halpern, Stuart A. Kurtz, Raimund Seidel

Editors:

Martin Abadi  Greg Frederickson John Mitchell
Pankaj Agarwal Andrew Goldberg Ketan Mulmuley
Eric Allender Georg Gottlob Gil Neiger
Tetsuo Asano  Vassos Hadzilacos David Peleg
Laszló Babai  Juris Hartmanis Andrew Pitts
Eric Bach  Maurice Herlihy James Royer
Stephen Brookes Stephen Homer  Alan Selman
Jin-Yi Cai Neil Immerman Nir Shavit
Anne Condon  †Paris Kanellakis Eva Tardos
Cynthia Dwork Howard Karloff  Sam Toueg
David Eppstein Philip Klein  Moshe Vardi
Ronald Fagin  Phokion Kolaitis Jennifer Welch
Lance Fortnow Stephen Mahaney Pierre Wolper
Steven Fortune Michael Merritt

Managing editor: Michael J. O’Donnell

Electronic mail: chicago-journal@cs.uchicago.edu

[ii] Gerstel, Cidon, Zaks Optimal Virtual Path Layout in ATM (Info)

This article is included in the special issue, Selected Papers from PODC 1994, containing articles based on extended abstracts presented at the 13th Annual ACM Symposium on Principles of Distrituted Computing, Los Angeles, California, August 1994. This special issue was edited by David Peleg.

[iii]

Optimal Virtual Path Layout in ATM Networks with Shared Routing Table Switches

Ornan Gerstel  Israel Cidon  Shmuel Zaks

31 October, 1996

Abstract

In this paper we present a new model for routing that occurs in

Abstract-1

high-speed ATM networks. Within this model we define a general routing problem, called a virtual path layout. Given a network of nodes (switches) and links, one must find a set of paths in the network, termed the virtual path layout, whereby each pair of nodes may connect using a route that is a concatenation of a small number of virtual paths and is also short in terms of the network links it traverses. Each such layout implies a utilization of the routing tables in the network’s nodes. Our goal is to find a layout that minimizes this utilization, assuming that each such node has a central routing table. We prove that this problem is NP-complete, and consequently focus on a simpler problem, in which it is required to connect all nodes to a single switch. Next, we prove that even this problem is NP-complete, and restrict some of the assumptions to yield a practical subproblem, for which we present a polynomial-time greedy algorithm that produces an optimal solution. Finally, we use this restricted problem as a building block in finding a suboptimal solution to the original problem. The results exhibit a tradeoff between the performance of a routing scheme and its resource utilization.

This article contains results that were presented at the 13th Annual ACM Symposium on Principles of Distributed Computing [GZ94].

1 Gerstel, Cidon, Zaks Optimal Virtual Path Layout in ATM

1 Introduction

1.1 Background

The advent of fiber optic media has dramatically changed classical views on

1.1-1

the role and structure of digital communication networks. Specifically, the sharp distinction (in terms of node hardware architectures, network management techniques, routing schemes, and various theoretical aspects) between telephone networks, cable television networks, and computer networks, has been replaced by a unified approach. In this integrated approach (termed B-ISDN), real-time, high-quality video and audio, and very large amounts of data are integrated into a single digital network that will support numerous applications—ranging from interactive television, video conferencing systems, and video-phone to distributed virtual reality systems.

While fiber optic cables are capable of transferring very large amounts

1.1-2

of data (around 10^{10} bits per second), the nodes that connect these cables cannot accommodate this flood of data in software. For this reason, the routing of data packets, which is traditionally done by the network layer software, has been moved to special-purpose very fast hardware, a fact that requires very simple routing algorithms.

The most common solution for this new network architecture is called

1.1-3

Asynchronous Transfer Mode (ATM for short), and is thoroughly described in the literature [ITU90, HH91, LB92, CS94] ^{1}. ATM is based on relatively small fixed-size packets called cells. Each cell is routed independently, based on two small routing fields at the cell header, called the virtual channel index (VCI) and the virtual path index (VPI).

At each intermediate node, these fields serve as indices to two routing

1.1-4

tables (the VCI serves as an index to one table, and the VPI to the other), and the routing is done in accordance with predetermined information from the appropriate entries (which is entered into the tables during the setup of connections in the network).

Routing in ATM is hierarchical in the sense that the VCI of a cell is

1.1-5

ignored as long as its VPI is not null. This algorithm effectively creates two types of predetermined simple routes in the network: routes that are based on VPIs (called virtual paths or VPs), and routes that are based on VCIs (called virtual channels or VCs). The latter may be viewed as a concatenation of complete VPs.

Gerstel, Cidon, Zaks Optimal Virtual Path Layout in ATM §1.2

2 VPs and VCs have different roles in the network. While VCs are used for

1A different approach to fast routing is based on automatic network routing (ANR)

and was implemented in PARIS and plaNET [ACG^{+}90, CG88, CGG^{+}92].

1.1-6

creating connections between two users of the network that wish to communicate (e.g., a telephone call), VPs have an internal network role (decreasing the overhead caused by network management activities), and are used for bundling several VCs that share part of their route.

The VC and VP concepts have been extensively discussed in the com-

1.1-7

munications literature; however, to the best of our knowledge, the problem of how VPs should be laid out in a given communication network has never been addressed analytically. A few heuristics have been proposed and experimented [ATTD94, HKIT94]. This problem is of practical importance, since the layout of VPs in a network determines many of the network’s important performance characteristics, such as the overhead and delay of the setup of a new VC, the load on the VP routing tables, and various fault-tolerance qualities.

1.2 Our Work

All of the above calls for a new model—different from the classical model

1.2-1

for routing in computer networks—for both describing the network and measuring the performance of algorithms on it. In Section 2 we define a model for routing in ATM networks, and determine the essential characteristics for measuring the optimality of a given layout. Using this model, we define the general layout problem for ATM. We then isolate a simpler case, which can be viewed as a variant of tree routing (analogous to the way that interval routing [SK85] is used in classical routing problems), suited for this model.

In Section 3 we prove that even the simpler case is NP-complete, and

1.2-2

we therefore restrict ourselves to a subproblem that is general enough for practical purposes, and present a greedy algorithm that optimally solves the subproblem for any given tree network. In Section 4 we prove the general problem to be NP-complete as well, and demonstrate the use of the subproblem as a building block in the solution of the general problem on arbitrary networks. We conclude in Section 5 by summing up the results in the paper, and presenting open problems.

We expect our contribution to be three-fold:

1.2-3

1. This paper is among the first to analytically address the problem (together with [CGZ94]). For this reason, we focus on a relatively simple problem, with a low number of parameters. This is also a first attempt

3 to prove complexity results concerning the problem, and to present an optimal solution for a special case (the one-to-many layout problem on trees—see Definition 5).

2. We believe the problem we focus on is of practical importance in certain scenarios in ATM networks. In particular, our problem is most suitable for an environment with short-lived VCs without an a priori known bandwidth; such environments are expected to be typical for distributed applications over ATM networks [LPS91]. Even our restricted (polynomially solvable) problem seems to be useful for client-server applications over ATM.

3. We present basic techniques for deriving upper and lower bounds on such problems (exemplified by the tree-routing problem, often used as a benchmark case study). In particular, the crux of our greedy algorithm (i.e., the upper bound) is nonintuitive in nature, and was formulated by the needs of its optimality proof (lower bound).

The present paper is closely related to [CGZ94], in which a similar model

1.2-4

is discussed, using a different VP-table load metric (on the edges of the graph rather than on its nodes). This difference stems from different node implementations, and seems to have an impact on the complexity of the problem. In particular, we present here NP-completeness results that we were unable to derive for the other load metric.

The simpler one-to-many problem on trees is addressed in [CGZ94] as

1.2-5

well, using a different technique that is based on dividing the tree into small subtrees and solving the problem separately in each subtree. This technique yields a solution that is asymptotically optimal under certain assumptions. In contrast, the “greedy” technique presented herein provides an optimal solution for any given tree. Also, the resulting algorithm is much simpler to implement, and has lower time complexity. Furthermore, while manyto-many solutions in [CGZ94] yield high VP-table loads, the solution herein results in much smaller loads, by compromising the efficient utilization of the physical network (using the concept of a stretch factor).

A related problem is that of keeping small routing tables for routing

1.2-6

in conventional computer networks. This problem has been widely studied [ABLP89, AP92, FJ86, FJ88, KK77, KK80, PU88] and has yielded interesting graph decompositions and structures, but it differs from ours in some major aspects, which deemed most of these solutions impractical for

Gerstel, Cidon, Zaks Optimal Virtual Path Layout in ATM §2

4 our purposes. The main difference stems from the fact that in our case there is no flexibility as to the routing scheme itself, since this is determined by the ATM standard [ITU90]. We therefore present a static structure in the network, while in the conventional model, the exact routing of a packet may be determined dynamically during the process of its routing (as in [AP92, ABLP89]), or by information that is based on the name of the destination (as in [FJ86, FJ88]).

Other differences stem from practical restrictions on the model, in which

1.2-7

the routing tables of each node are restricted by the same size, while in some of the conventional solutions the total (or average) size of the routing tables is minimized (e.g., [FJ86, FJ88, PU88]).

Our approach resembles some of the above-mentioned techniques in that

1.2-8

a simpler tree-routing problem is used as a building block in the general-case solution (analogous to the way that interval routing on trees [SK85] is used in some of the routing schemes for arbitrary graphs). We use the techniques of [AP92] for demonstrating the usage of our tree-routing problem in solving the general problem.

This paper is an extension of [GZ94].

1.2-9

2 The Model

We first define a graph-theoretic model for our problems (for basic terms and

2-1

definitions, see [Eve79]). In our model, we have an underlying communication network that consists of nodes and links between nodes. This network is modeled by an undirected graph G = (V, E), where V corresponds to the set of nodes and E to the set of physical links between them.

Due to the routing mechanism in ATM, VPs are unidirectional paths in

2-2

the network. However, for connection management reasons [CS94], VPs are coupled together in pairs of parallel routes in opposite directions, effectively creating bidirectional paths. For simplicity, we refer in the remainder of the paper to these bidirectional VPs exclusively.

A virtual path layout is a set of simple bidirectional paths on the given

2-3

network, as formalized by the following definition:

Definition 1 Let P(G) be the set of all simple paths in G. A virtual path layout or VPL is a subset of P(G). Formally, it is convenient to represent a VPL Ψ by a pair Ψ = (G_{Ψ}, I), where G_{Ψ} = (V, E_{Ψ}) is a “virtual” graph and

5 I: E_{Ψ} → P(G) is a “mapping” function. A “virtual” edge ψ = (a, b) ∈ E_{Ψ} represents a VP between the nodes a and b. The function I(ψ) maps each virtual edge ψ = (a, b) to its corresponding route in G. We term this path the induced path of ψ.

For the sake of notational convenience, we refer to a path p ∈ P(G) either as a set of edges or as a set of nodes.

We extend the definition of I to simple paths in G_{Ψ} as follows:

2-4

Definition 2 The induced path I(p), for a path p ∈ P(G_{Ψ}), where p = (ψ_{1}, ψ_{2}, …, ψ_{k}) and ψ_{i} ∈ E_{Ψ} for every i, is the path obtained by concatenating the induced paths I(ψ_{i}) of all ψ_{i}s.

Each VP utilizes an entry^{2} in the routing table of each node that is part of

2-5

its path (be it an endpoint or an intermediate node). Since the routing tables are bounded by the ATM standard to 4,096 entries, this resource should be carefully allocated in large networks. The following load measure expresses this utilization, assuming that each node has a central, shared routing table:^{3}

Definition 3 The load L(v) on a node v ∈ V is the number of VPs ψ ∈ E_{Ψ} that include v in their induced paths, namely, L(v) = |{ ψ ∈ E_{Ψ} | v ∈ I(ψ) }|. The load definition is extended to a VPL Ψ by L(Ψ) = max_{v∈V} L(v).

Definition 4 Let μ ∈ ℝ be a real number called the stretch factor. The hop count H_{μ}(v, w) for a pair of nodes v, w ∈ V is the minimum k such that:

1. ∃p = (Ψ_{1}, Ψ_{2}, …, Ψ_{k}) ∈ P(G_{Ψ}), (Ψ_{i} ∈ E_{Ψ} for every i),

2. ∃x, y ∈ V, ψ_{1} = (v, x), ψ_{k} = (y, w), and

3. the induced path I(p) is at most μ times longer than the shortest path between v and w in G.

If no such path exists, define H_{μ}(v, w) = ∞ (this does not necessarily mean that G_{Ψ} is not connected).

6 We distinguish between two problems:

2A VP actually uses two entries in each such routing table, for the two unidirectional VPs from which it is composed, but we neglect this fact, as it exactly doubles the utilization at any table.

3This alternative is applicable mainly for nodes that are based on shared memory.

Other node architectures are based on a separate processor for each link in the node, which dictates a separate routing table for each link, and a different load measure.

2-6

• the general layout problem in which it is required to connect every pair of nodes in V —we term this access pattern “many-to-many” (m-m for short), and

• a more restricted access pattern in which it is required to connect all nodes to a single node (called the root)—we term this access pattern “one-to-many” (1-m).

The VPL for m-m access is denoted by VPL^{m-m}, while a VPL for 1-m access is denoted by VPL^{1-m}. Note that VPL^{1-m} differs from broadcasting in that the data is not distributed from the root to all other nodes in the network, but rather, it enables separate connections (VCs) from the root to all the other nodes.

The two problems are formalized by the following definition.

2-7

Definition 5 Let h > 0; μ ≥ 1; let G = (V, E) be a given network; and let r ∈ V. The following two cases correspond to the above-mentioned problems.

• A VPL^{m-m} in G is h-feasible if max_{v,w∈V} H_{μ}(v, w) ≤ h.

• A VPL^{1-m} in G is (h, r)-feasible if max_{v∈V} H_{μ}(v, r) ≤ h.

The feasibility of a VPL captures the notion of a network that has good

2-8

worst-case performance (since h determines the maximum number of VPs that are needed for the compositions of any VC, and this number is proportional to the time that the creation of that VC takes). We now define an optimal solution as a solution that does not require much of the network resources, while maintaining this good performance (the load on a node is proportional to the required capacity of the VP routing tables, as well as other resources).

Definition 6 Let h > 0 and μ ≥ 1. A VPL^{m-m} Ψ is h-optimal if it is hfeasible and its load L(Ψ) is minimal among all other h-feasible VPLs. This definition is extended in a straightforward manner to the (h, r)-optimality of a VPL^{1-m} with a root r.

Example 1 Consider the ATM network with VPs in Figure 1, in which there

Example 1-1

are three VCs, one between user x1 and user x2 (we denote it by VC (x1, x2)), one between y1 and y2, and one between z1 and z2. All VCs are composed

7

b c  d f  virtual path virtual channel physical link ga x1 y1 z1y2  x2 z2  an end user x2 node e

Figure 1: An example for VP/VC layout 8

Chicago Journal of Theoretical Computer Science 1996-3 of a concatenation of VPs (e.g., VC (y1, y2) is composed of VP(a, b) and VP(b, g)).

Since the routing of cells from a to b is done on VP(a, b), there is no need

Example 1-2

for a separate entry in the VC routing table of c for each such VC, and this remains true even if there are many VCs that use VP(a, b) as part of their route. Only at b there is an entry for each of the VCs, since the VP(a, b) ends there, to determine if the VC continues into VP(b, d) (for VP(x1, x2)) or into VP(b, g) (for VC (y1, y2) and VC (z1, z2)).

Since each VC is composed of complete VPs, there is no way to create

Example 1-3

a VC between a and c, despite the fact that the physical network itself is connected (hence H_{μ}(a, c) = ∞).

Example 1-4 Note that if μ < \frac{5}{3}, then H_{μ}(a, e) = ∞, since the shortest path d_{G}(a, e) = 3 and the path induced by the VPs (a, b), (b, d), (d, e) ∈ E_{Ψ} is of length 5 (since p = ((a, b), (b, d), (d, e)) and I(p) = I((a, b)), I((b, d)), I((d, e)) = (a, c, b, c, d, e)); If, however, μ > \frac{5}{3}, then H_{μ}(a, e) = 3. As to the load measure, L(c) = |{(a, b), (b, d), (e, f)}| = 3 and L(d) = |{(b, d), (e, d), (e, f)}| = 3.

3 Tools

Our formulation of the optimal VPL^{1-m} algorithm and its optimality proof

3-1

are based on some vector notations, definitions, and properties, which are presented in this section.

Notation 1 Let V, W ∈ ℕ^{h}, c ∈ ℕ, and i, j ∈ {1, …, h}. We use the following notations:

• V [i]—the ith element in the vector V,

• ∥V ∥—the sum of the elements V [i] (since all elements are positive, this is the L_{1} norm of the vector, often written ∥V ∥_{1}),

• V [i: j]—the part of the vector from the ith to the jth position (inclusive),

• c⃗[1: i]—the vector (c, …, c) of i elements that are equal to c,

• V • W —the concatenation of the vectors V and W,

• V + W —the vector sum of V and W, and

9 • V < W —the lexicographic comparison between vectors, using an or-

der in which V [1] is the least-significant component, e.g., (9, 11, 1) < (2, 12, 1) < (0, 0, 2). The same applies for >, ≤, and ≥.

We shall need the following properties of vectors in ℕ^{h}.

3-2

Lemma 1 Let L, M be vectors in ℕ^{h} for some h > 1, such that ∥L[1: h − 1]∥ ≤ 1 and M ≥ L. Then ∥M∥ ≥ ∥L∥.

Proof of Lemma 1 If M ≥ L, then one of the following holds:

Case 1 M[1: h − 1] ≥ L[1: h − 1] and M[h] = L[h]: Clearly

∥M[1: h − 1]∥ ≥ ∥L[1: h − 1]∥

hence

∥M∥ = ∥M[1: h − 1]∥ + M[h] ≥ ∥L[1: h − 1]∥ + M[h] = ∥L∥

Case 2 M[h] > L[h]: Then

∥M∥ ≥ M[h] ≥ L[h] + 1 ≥ L[h] + ∥L[1: h − 1]∥ = ∥L∥

Proof of Lemma 1 □

3-3

Definition 7 A vector L is called k-nontrivial if ∥L[1: k − 1]∥ ≤ 1 and ∥L[1: k]∥ > 1. In particular, if L[1] > 1 it is 1-nontrivial, and if ∥L∥ ≤ 1, then L is ∞-nontrivial. A vector is k^{(>)}-nontrivial if it is x-nontrivial for some x > k (similar definitions apply for <, ≤, and ≥).

Definition 8 Let S be a sequence of vector pairs in ℕ^{h}, S = ((L_{i}, M_{i}))_{i=1}^{s}. S is proper if the following properties hold:

P1: L_{i} ≤ M_{i} for every i ∈ {1, …, s}, and

P2: if i > j, then there exists k > 0 such that L_{j}[1: k] ≥ L_{i}[1: k], L_{j} is k-nontrivial, and L_{i} is k^{(≥)}-nontrivial.

10 Notation 2 We shall need the following additional vector notations, where L is an arbitrary vector of length h, S = ((L_{i}, M_{i}))_{i=1}^{s}.

• The transformation L^{trans(j)} on a vector L is defined by: L^{trans(0)} = L, and L^{trans(j)} = 0[1: j] • (L[j + 1] + 1) • L[j + 2: h] for j > 0.

• S_{L} = (L_{i})_{i=1}^{s}, and S_{R} = (M_{i})_{i=1}^{s}.

• Σ((L_{i})_{i=1}^{s}) = ∑_{i=1}^{s} L_{i}.

• Let P = (p_{1}, p_{2}, …, p_{s}) where 0 ≤ p_{i} ≤ h − 1. Then S^{trans(P)} = (L_{i}^{trans(p_{i})})_{i=1}^{s}.

Consider a proper sequence S = ((L_{i}, M_{i}))_{i=1}^{s}. Clearly Σ(S_{L}) ≤ Σ(S_{R}).

3-4

Note that the transformation L_{i}^{trans(j)} of a vector in S increases L_{i} lexicographically. So, the sum of the L_{i} vectors, after transforming L_{i}^{trans(j)}, may become lexicographically larger than the sum of the M_{i}s. That is, in some cases Σ(S_{L}^{trans((0,...,0,j,0,...,0))}) > Σ(S_{R}), even though S is proper. To solve this problem, we first show that if the total sum of values in the M_{i} vectors (∥Σ(S_{R})∥) is less than that of the L_{i} vectors, one of the L_{i}s can indeed be transformed without violating the overall lexicographic order, that is: Σ(S_{L}^{trans((0,...,0,j,0,...,0))}) ≤ Σ(S_{R}).

Lemma 2 Let S = (L_{i}, M_{i})_{i=1}^{s} be a proper sequence, and let ∥Σ(S_{R})∥ < ∥Σ(S_{L})∥. Then there exist integers 0 < p ≤ h − 1 and 0 < k ≤ s such that Σ(S_{L}) ≤ Σ(S_{R}), where P = 0[k − 1] • p • 0[1: s − k].

Proof of Lemma 2 Let L_{k} be the first vector in S_{L} that is p-nontrivial for

Proof of Lemma 2-1

p < ∞. Such a choice of k exists, since otherwise ∥Σ(S_{L})∥ ≤ ∥Σ(S_{R})∥ by Lemma 1.

Clearly ∥L_{k}^{trans(p)}∥ < ∥L_{k}∥. If L_{k}[p+1: h] < M_{k}[p+1: h], then L_{k}^{trans(p)} ≤ M_{k}

Proof of Lemma 2-2

and Σ(S_{L}) ≤ Σ(S_{R}), as required by the lemma. Otherwise, if L_{k}[p + 1: h] = M_{k}[p + 1: h] (and therefore L_{k}^{trans(p)} > M_{k}), then two cases are possible:

Case 1 For every j > k, L_{j}[p + 1: h] = M_{j}[p + 1: h]: Then ∥L_{j}∥ ≤ ∥M_{j}∥ since L_{j} is p^{(≥)}-nontrivial, and hence L[1: p], M[1: p] satisfy the conditions of Lemma 1. But, since ∥L_{i}∥ ≤ ∥M_{i}∥ for every i < k, we have ∥Σ(S_{L})∥ ≤ ∥Σ(S_{R})∥, contradicting the conditions of the lemma.

11

\begin{aligned}( & L_{1} ≤ M_{1} ; ⋮ ; L_{k} ≤ M_{k} ; ⋮ ; L_{j} < M_{j} ; ⋮ ; L_{s} ≤ M_{s} & ) \\ & (a) \end{aligned} → \begin{aligned}( & L_{1}  ≤ M_{1} ; ⋮ ; L_{k}^{trans(p)} ? M_{k} ; ⋮ ; L_{j}  < M_{j} ; ⋮ ; L_{s}  ≤ M_{s} & ) \\ & (b) \end{aligned} →

L_{1}  ≤ M_{1}

⋮

L_{k}^{trans(p)} ≤ M_{k}^{dir}

⋮

L_{j}  ≤ M_{j}^{indir}

⋮

L_{s}  ≤ M_{s}

(c)

Figure 2: Transformations in Case 2 of Lemma 2

Case 2 There exists j > k such that L_{j}[p + 1: h] < M_{j}[p + 1: h]: We transform the M_{k} and M_{j} vectors so as to keep the lexicographic order in the kth and jth pairs, without changing the sum Σ(S_{R}), thereby proving the lemma (refer to Figure 2). The transformations are as follows.

M_{k}^{dir} = M_{j}[1: p] • (M_{k}[p + 1] + 1) • M_{k}[p + 2: h]
M_{j}^{indir} = M_{k}[1: p] • (M_{j}[p + 1] − 1) • M_{j}[p + 2: h]

Clearly M_{k} + M_{j} = M_{k}^{dir} + M_{j}^{indir} and therefore ∑_{j=1}^{s} M_{j} = Σ(S_{R}). It is also clear that L_{k}^{trans(p)} ≤ M_{k}^{dir}. The lexicographic order still holds for the jth pair (L_{j} ≤ M_{j}^{indir}), because L_{j}[p + 1: h] ≤ M_{j}^{indir}[p + 1: h] and L_{j}[1: p] ≤ L_{k}[1: p] ≤ M_{k}[1: p] = M_{j}^{indir}[1: p].

Proof of Lemma 2 □

We now use Lemma 2 repeatedly to show that it is possible to decrease

3-5

the total sum of values in all the L vectors (∥Σ(S_{L})∥) without increasing their total lexicographic order (Σ(S_{L})) too much.

Lemma 3 Let S = ((L_{i}, M_{i}))_{i=1}^{s} be a proper sequence. Then there exists a vector of integers P = (p_{1}, p_{2}, …, p_{s}) such that the following conditions hold:

12 1. 0 ≤ p_{i} ≤ h − 1 for every i,

2. Σ(S_{L}^{trans(P)}) ≤ Σ(S_{R}), and

3. ∥Σ(S_{L}^{trans(P)})∥ ≤ ∥Σ(S_{R})∥.

Proof of Lemma 3 Starting with P = (0, …, 0), we gradually increase

Proof of Lemma 3-1

the coordinates of P until Condition 3 holds, while preserving Condition 2. Note that for the initial P = (0, …, 0), Condition 2 holds: Σ(S_{L}^{trans(P)}) = Σ(S_{L}) ≤ Σ(S_{R}) (the left equality holds by definition of L_{i}^{trans(0)}, and the right inequality is due to Property P1 for each pair in S). The transformations implied by the changes in P may, however, violate P1 (i.e., L_{i}^{trans(p_{i})} may become lexicographically greater than M_{i}). In order to avoid such violations (and thereby preserve Condition 2), we use Lemma 2.

In this process, we have advanced toward satisfying Condition 3, since

Proof of Lemma 3-2

now ∥L_{i}^{trans(p_{i})}∥ ≤ ∥M_{i}∥, while this did not necessarily hold for ∥L_{i}∥ and ∥M_{i}∥. Before the next change in P, S must be rearranged to remain proper. To this end, the vectors in S need to be transformed as in Lemma 2 to maintain Property P1. In addition, they may need to be reordered so as to keep Property P2. However, these changes do not alter Σ(S_{R}).

Since ∥Σ(S_{L})∥ decreases each time Lemma 2 is applied, after a finite

Proof of Lemma 3-3

number of applications of Lemma 2, it will become smaller than ∥Σ(S_{R})∥.

Proof of Lemma 3 □

4 The VPL^{1-m} Problem

In this section we discuss the VPL^{1-m} problem on tree networks. Our main

4-1

result is an optimal polynomial algorithm for this case and its proof of optimality, based on tools from the previous section. Before going into the details, we mention that this problem is hard for general topologies, assuming an unbounded stretch factor (i.e., μ = ∞). In other words, given the following decision problem:

Problem: The Optimal VPL^{1-m} problem (OPT-VPL^{1-m}).

Instance: An undirected graph G = (V, E), a node r ∈ V, integers L, h > 0.

Question: Assuming μ = ∞, does there exist Ψ, an (h, r)-feasible VPL^{1-m}

on G such that L(Ψ) ≤ L? 13

→^{root}  ^{sink}^{source}  ^{edge, capacity 1}^{edge, capacity L}^{edge, capacity ∞}

Figure 3: Transforming the VPL^{1-m} problem into a flow problem

We prove that OPT-VPL^{1-m} is NP-complete. The details of the proof

4-2

may be found in Appendix A.1.

Observation 1 It is interesting to note that the variant of OPT-VPL^{1-m} problem with fixed h = 1 can be solved polynomially. This is done by the transformation depicted in Figure 3, which transforms the (undirected) graph of the VPL^{1-m} problem into a (directed) flow problem. Each undirected edge is replaced by five edges and two new nodes, where the edge between these new nodes is restricted to a capacity of L, and the other edges do not have capacity restrictions. A new source node is added and connected to all the original nodes except the root r by edges of capacity 1. The original root node is defined as the sink.

We now present a polynomial-time optimal solution for VPL^{1-m}, assum-

4-3

ing μ = 1 and a tree network. These restrictions still allow a variety of applications for the problem. In particular, this restricted VPL^{1-m} problem is used as a building block for solving the VPL^{m-m} problem. In addition, it has practical applications of its own, in the field of client-server applications over ATM [LPS91]. The problem also serves as a sufficiently complex case to allow for a presentation of nontrivial upper and lower bound results, using techniques which we expect to be basic in similar future studies.

14

4.1 The Algorithm

We devise a greedy algorithm that produces an optimal VPL^{1-m} for any tree.

4.1-1

This algorithm is an iterative process in which the minimal load is guessed by the main procedure, which calls the find_layout procedure with the guessed load as a parameter. The find_layout procedure tries to construct a layout under the given load constraint, and informs the main if the guess enabled the construction of the layout. Using this information, main increases or decreases its guess, until it achieves a minimal guess for which find_layout succeeds. Let vectarray represent the type array[V (T)] of ℕ^{h}.

0. procedure main(h: ℕ, T: tree, root: V (T))

1. var L1, L2: vectarray

2. find L_{max} ∈ {1, …, |V (T)|} such that

3. find_layout(h, T, root, L_{max}, L1) = success and

4. find_layout(h, T, root, L_{max} − 1, L2) = failure

5. construct_layout(root, L1)

6. end procedure main

In the find_layout procedure, we view the tree T as rooted at root. The

4.1-2

procedure starts from the leaves of the tree and advances toward the root. For each node v it maintains the number of VPs that go through v (and contribute to its load). This number is kept in a vector L_{v} ∈ ℕ^{h}, where L_{v}[1] holds the number of VPs that serve only as a first hop from some descendant, and L_{v}[i] holds the number of VPs that are an ith hop^{4} for some descendant x, but not an (i + 1)th hop for any descendant.

Specifically, find_layout creates a first-hop VP for each leaf (at line 4).

4.1-3

At an internal node v, the vector L_{v}, of VPs is equal to the vector sum of all the VPs that arrive at it from all its sons, plus one additional first-hop VP from v toward the root (at line 14). If this vector is too big (i.e., ∥L_{v}∥ exceeds the current load constraint at line 15), then the VPs that go through v are reduced by stopping some of them at the sons of v (hence turning the VP that starts at that son from a first-hop VP to an (i + 1)th hop VP), by applying the transformation in Figure 4 (at lines 16–21).

15 0. function find_layout(h: ℕ, root: V (T), L_{max}: ℕ, var L: vectarray)

4The shortest path, in terms of VPs, from x toward the root includes the VP as the ith VP from it.

1. returns {success , failure }

2. (L_{v} indicates the entry of L indexed by v)

3. for all w ∈ V (T)

4. if w is a leaf then L_{w} ← (1, 0, …, 0)

5. else L_{w} ← UNDEFINED

6. end if

7. end for

8. loop forever outer

9. if v = root then return success end if

10. find v ∈ V (T) such that

11. L_{v} = UNDEFINED and

12. for all x ∈ Sons(v), L_{x} ≠ UNDEFINED

13. loop forever inner

14. L_{v} ← ∑_{s∈Sons(v)} L_{s} + (1, 0, …, 0)

15. if ∥L_{v}∥ ≤ L_{max} then exit loop inner end if

16. find s ∈ Sons(v), i ∈ {1, …, h − 1} such that

17. ∥L_{s}[1: i]∥ > 1 and

18. for all s′ ∈ Sons(v) \ {s}, L_{s}[1: i] ≥ L_{s′}[1: i] (lexicographic)

19. for all s′ ∈ Sons(v), ∥L_{s′}[1: i − 1]∥ ≤ 1

20. if no such i, s exist then return failure end if

21. L_{s} ← 0[1: i] • (L_{s}[i + 1] + 1) • L_{s}[i + 2: h] (transform L_{s} to L_{s}^{trans(i+1)})

22. end loop inner

23. end loop outer

24. end function find_layout

→

j = 1 j = i + 1

j ≤ i

j > i
j ≤ i

j > i

Son Overloaded node

Figure 4: The transformation on an overloaded node v: L_{v} → L_{v}^{trans(i+1)}

A partial intuition behind this transformation is that it is better to stop

4.1-4

VPs that serve as a jth hop for the lowest possible j, as this does not increase the vector L_{v} too much in its lexicographic order. A part of this transformation is, however, nonintuitive, and stems directly from needs of the proof of optimality.

The main procedure relies on construct_layout for the actual creation

4.1-5

of the VPL^{1-m} from the set of vectors in L. This procedure is activated for a node v and recursively creates VPs for all the nodes in the subtree rooted at v. The code of construct_layout is straightforward, yet lengthy and involved, and is omitted in this paper. For similar reasons, we also omit the proof of correctness of the algorithm. Similar code and proofs may be found in [Ger95].

4.2 Proof of Optimality

We prove the solution that find_layout produces is optimal for every given

4.2-1

tree and h, thereby implicitly proving a lower bound for the VPL^{1-m} problem. The main lemma is Lemma 6, in which the solution { L_{v} | v ∈ V }

17 of find_layout is compared to an arbitrary minimal solution with a vector representation { M_{v} | v ∈ V }. To this end, we first prove (in Lemma 5) that every minimal solution indeed has a vector representation with some desired properties. In this representation, ∥W_{v}∥ is the load on node v. Using the tools in Section 3, in particular Lemma 3, we prove (by induction) that at every node v, L_{v} ≤ M_{v} and ∥L_{v}∥ ≤ ∥M_{v}∥, thereby proving that the solution of find_layout has minimal load (and is thus optimal). The simple case for the proof is when v is not overloaded, in which case L_{v} = ∑_{s∈Sons(v)} L_{s} + (1, 0, …, 0), and the inductive claim easily follows, assuming it holds for each son of v. For an overloaded node, the load vectors of the sons are arranged in the order that they are chosen by find_layout at lines 15–16. This order is reflected by Property P2 of a proper sequence (see Definition 8). Then, they are lexicographically compared to the respective M vectors.

Thus, before applying transformations on any son of v, we have L_{i} ≤ M_{i},

4.2-2

i = 1, …, s. Using Lemma 3, we show that after several transformations the total load at v, ∥Σ(S_{L})∥, decreases at least to the level of the given optimal solution (∥Σ(S_{R})∥), while maintaining its property of being lexicographically minimal.

The above sketch is formalized as follows.

4.2-3

Definition 9 Let ℏ(ψ) denote the maximal hop count for which ψ serves from some node to the root (this is the value j = i + 1 assigned to the VP starting at the son in Figure 4.

Definition 10 Given h > 0, a VPL^{1-m} is (h, r)-minimal if it is (h, r)-feasible and the deletion of a VP ψ ∈ E_{Ψ} yields a VPL^{1-m} that is not (h, r)-feasible.

Lemma 4 In a minimal VPL^{1-m}, there exists a unique VP ψ_{v} for every node v that starts at v toward the root.

Proof of Lemma 4 Assuming two such VPs ψ_{1} and ψ_{2} exist in a minimal VPL^{1-m}, consider the paths p_{i} (i = 1, 2) from v to the root that start with ψ_{i}. Without loss of generality, p_{1} is not longer than p_{2} (in terms of VPhops). Therefore, we can remove ψ_{2} from the VPL^{1-m} without damaging its feasibility, contradicting the minimality assumption.

Proof of Lemma 4 □

18 Note that the previous lemma implies that the virtual graph G_{Ψ} of a

4.2-4

minimal VPL^{1-m} on a tree, is a tree as well.

Lemma 5 Given h > 0, let T be a tree rooted at r. Every (h, r)-minimal VPL^{1-m} on T can be represented by a set of vectors { M_{v} ∈ ℕ^{h} | v ∈ V (T) }, such that for every node v, the following conditions hold:

1. L(v) = ∥M_{v}∥,

2. if v is a leaf then M_{v} = (1, 0, …, 0), and

3. M_{v} ≥ ∑_{s∈Sons(v)} M_{s} + (1, 0, …, 0).

Proof of Lemma 5 Let T_{v} denote the set of nodes in the subtree below v. Define M_{v} for a node v by

M_{v}[i] = |{ ψ ∈ E_{Ψ} | v ∈ ψ ∧ ℏ(ψ) = i }|

Condition 2 is trivially satisfied. Condition 1 is satisfied since each VP that includes the node v contributes one to a single M_{v}[i] (according to the value of ℏ(ψ)), hence L(v) = ∥M_{v}∥. To prove Condition 3, let ψ_{v} be the VP starting at v. Note that if H(ψ_{v}) = 1 then no VP stops at v, and every VP that loads a son of v loads v as well, which has an additional load incurred by ψ_{v}, hence M_{v} = ∑_{s∈Sons(v)} M_{s} + (1, 0, …, 0). If H(ψ_{v}) = i > 1 then a VP ψ that stops at v has H(ψ) ≤ i − 1, hence M_{v}[i: h] = ∑_{s∈Sons(v)} M_{s}[i: h] + (1, 0, …, 0) and M_{v} > ∑_{s∈Sons(v)} M_{s} + (1, 0, …, 0).

Proof of Lemma 5 □

Lemma 6 Given h > 0, if there exists an (h, r)-feasible VPL^{1-m} Ψ with L(Ψ) ≤ X for some X > 0 with a vector representation { M_{v} | v ∈ V (T) }, then for every node v ≠ r the following holds:

• If L_{max} = X then find_layout does not return failure while handling v, and

• the vector L_{v} produced by find_layout satisfies L_{v} ≤ M_{v}.

Proof of Lemma 6 We use induction on the height H of the subtrees of T.

Proof of Lemma 6-1

Basis. For a tree of height H = 0 (i.e., a leaf), it is clear that L_{v} = M_{v} =

Proof of Lemma 6-2

(1, 0, …, 0).

19 Induction step. Assume that the claim holds for subtrees of height at most

Proof of Lemma 6-3

H − 1, and let v be a node such that T_{v} is of height H. By the induction hypothesis, find_layout does not return failure for every son s of v and L_{s} ≤ M_{s}. Let L′_{v} = ∑_{s∈Sons(v)} L_{s} + (1, 0, …, 0).

If ∥L′_{v}∥ ≤ X then find_layout will continue all VPs through v (no trans-

Proof of Lemma 6-4

formations are performed), in which case, (1) it does not return failure while handling v, and (2) the vector L_{v} = L′_{v} ≤ ∑_{s∈Sons(v)} M_{s}+(1, 0, …, 0) ≤ M_{v}.

The case when ∥L′_{v}∥ > X is proven as follows. Arrange the load vectors

Proof of Lemma 6-5

of the sons of v in the order they are chosen at lines 16–19 (which is the order determined by Property P2 of Definition 8), and add a pair of (1, 0, …, 0) vectors to this sequence. The sequence that includes these load vectors and the corresponding M vectors is proper.

(1, 0, …, 0) ≤ (1, 0, …, 0)
L_{1} ≤ M_{1}
L_{2} ≤ M_{2}
⋮
L_{s} ≤ M_{s}

By Lemma 3, there exists a vector P = (p_{1}, …, p_{s}) of integers 0 ≤ p_{i} ≤

Proof of Lemma 6-6

h − 1 such that Σ(S_{L}^{trans(P)}) ≤ Σ(S_{R}) and ∥Σ(S_{L}^{trans(P)})∥ ≤ ∥Σ(S_{R})∥. Note that Σ(S_{L}^{trans(P)}) is the value of the vector L_{v} after some finite number of iterations in the internal loop of find_layout for node v. The only way that find_layout may return failure is if no son that satisfies the conditions of lines 16–19 is found. In this case, all sons s have ∥L_{s}[1: h − 1]∥ ≤ 1. By Lemma 1, ∥L_{s}∥ ≤ ∥M_{s}∥ and hence X < ∥L′_{v}∥ ≤ ∥Σ(S_{R})∥—which is a contradiction to the feasibility of the given solution, since by Lemma 5 ∥Σ((_{R}S))∥ ≤ ∥M_{v}∥. Therefore we get Σ((_{L}S)^{trans(P)}) ≤ X and find_layout finishes handling v without returning failure with L_{v} ≤ M_{v}.

Proof of Lemma 6 □

The theorem that concludes the proof is:

4.2-5

Theorem 1 Given h > 0, the main procedure finds an (h, r)-optimal VPL^{1-m} for any given tree T with N nodes rooted at r, in O(hN log_{2} N) time.

20 Proof of Theorem 1 By Lemma 6, find_layout will successfully handle

Proof of Theorem 1-1

each son of r if L_{max} implies a feasible solution.

It remains to show that find_layout does not fail for the root r. This proof

Proof of Theorem 1-2

is identical to the induction step of Lemma 6, except that the (1, 0, …, 0) vectors are not added as part of the list (since no new VP starts at the root r). Hence, Lemma 3 is applied on the load vectors L_{i} produced by find_layout for the sons of r and on the load vectors M_{i} for those sons in some other VPL^{1-m}.

Therefore, find_layout will return success after handling the root (at

Proof of Theorem 1-3

line 9). It also returns a feasible layout that obeys L_{max}. Since main finds the minimal value for L_{max} for which find_layout returns success , it returns the optimal VPL^{1-m}.

As to the time complexity of this algorithm, the search for the optimal

Proof of Theorem 1-4

L_{max}, done by main, involves log_{2} N steps (by means of a binary search in the range 1, …, N for L_{max}). In each such step, find_layout is activated and scans the tree bottom up, during which time each node v is chosen once (at line 10) as the current node. Each node may also be chosen up to h times (at line 16) as a son to be transformed, since each transformation of L_{v} increases the number of zeros in it by at least one, and L_{v} has h values.

Proof of Theorem 1 □

The above algorithm does not imply a numerical bound of the load in-

4.2-6

curred by the layout; however, using a result from [CGZ94], it is easy to derive such a bound.

Lemma 7 For every tree network T, the VPL^{1-m} produced by main obeys L(Ψ) ≤ hN^{\frac{1}{h}}.

Proof of Lemma 7 Since main produces an optimal layout, it produces a better layout than the one suggested by [CGZ94] for which the load obeys L(Ψ) ≤ hN^{\frac{1}{h}}.

Proof of Lemma 7 □

5 The VPL^{m-m} Problem

In this section we use the algorithm for VPL^{1-m} to solve VPL^{m-m}, exempli-

5-1

fying our motivation for the definition of VPL^{1-m}. But first we note that the 21 VPL^{m-m} problem is a hard problem as well, by proving it is NP-complete for any odd hop count. The details of the proof may be found in Appendix A.2.

5.1 A Solution for General Graphs

We now present a suboptimal construction scheme, based on a technique of

5.1-1

[AP92], for the construction of “regional routing schemes” (used for regular routing problems).

The scheme is based on a clustering technique, which yields connected

5.1-2

overlapping subgraphs of a given graph, such that each pair of nodes with distance less than a given integer δ may be found together in at least one cluster. In each cluster we choose a center (i.e., the node that is closest to all the other nodes of the cluster), construct a breadth-first search tree to the center, and connect all the other nodes of the cluster to it by a VPL^{1-m} with μ = 1 and h′ = \frac{h}{2} (using the greedy algorithm of the previous section). Clearly, every pair of nodes whose distance is less than δ may be connected using no more than h hops via the pivot of their common cluster.

We repeat this scheme for increasing parameter δ (until the algorithm

5.1-3

yields one cluster that includes the whole network). To minimize the stretch factor μ, each pair is connected using the VPL^{1-m} of the smallest common cluster. Refer to Figure 5 for a graphic demonstration of this scheme.

We now present a precise definition of the above scheme. These definitions

5.1-4

are based on [AP92].

Definition 11 The j-neighborhood of a node v ∈ V is defined as

N_{j}(v) = { w | d_{G}(v, w) ≤ j }

The radius of a node wrt a graph is defined by

Rad(v, G) = max_{w∈V} d_{G}(v, w)

The radius of a graph is defined by

Rad(G) = min_{v∈V} Rad(v, G)

A center of a graph is a node for which Rad(v, G) = Rad(G).

22 chosen route

shortest route

pivot

cluster

Figure 5: VPL^{m-m} on a general graph

Definition 12 Given a set of nodes C ⊆ V, let G(C) denote the subgraph induced by C in G. A cluster is a subset C of nodes such that G(C) is connected. We use Rad(v, C) as a shorthand for Rad(v, G(C)). A cover is a collection of clusters C = { C_{i} | 1 ≤ i ≤ δ } such that ⋃_{i} C_{i} = V. Extend the definitions of radius by Rad(C) = max_{i} Rad(C_{i}). For a node v let Δ(C, v) denote the number of occurrences of v in the clusters C_{i}. The maximum degree of a cover C is defined as Δ(C) = max_{v∈V} Δ(C, v). Given two covers C = { C_{i} | 1 ≤ i ≤ δ } and T = { T_{i} | 1 ≤ i ≤ k } we say that T subsumes C if for every C_{i} ∈ C there exists a T_{j} ∈ T such that C_{i} ⊆ T_{j}.

We rely on the following theorem:

5.1-5

Theorem 2 ([AP92]) Given a graph G, a cover C, and an integer k ≥ 1, it is possible to construct a cover T that satisfies the following properties:

1. T subsumes C,

2. Rad(T ) ≤ (2k − 1)Rad(C), and

3. Δ(T ) = O(k |C|^{1/k}).

23 Intuitively, this theorem states that the graph can be divided into overlapping clusters, with three important properties:

1. For each node v there is a cluster that includes v, and all its δ-neighborhood (recall that δ is a parameter of the algorithm).

2. The distance between every pair of nodes in each cluster is not more than (2k − 1)δ.

3. Each node is included in not-too-many clusters (i.e., O(kN^{1/k})).

Our construction is based on the routing scheme from [AP92], combined

5.1-6

with the usage of VPL^{1-m} for trees. We first present a scheme that depends on a parameter δ, and then tune the scheme by choosing δ. The scheme connects pairs of nodes with a distance not exceeding δ.

0. function general_vpl(G: network, δ, k: ℕ) (δ, k > 0)

1. returns VPL^{m-m}

2. C ← { N_{δ}(v) | v ∈ V (G) }

3. Construct T as in Theorem 2

4. Select a center c in each T_{i}

5. Construct a VPL^{1-m} in each T_{i} to the center with h′ = \frac{h}{2}

6. return the union of all the above VPL^{1-m}s

7. end function general_vpl

Lemma 8 Let v, w be a pair of nodes such that d_{G}(v, w) ≤ δ and let the stretch factor be μ = 8k. Then the number of hops between v and w is H_{μ}(v, w) ≤ h in the VPL^{m-m} produced by algorithm general_vpl.

Proof of Lemma 8 Clearly, v ∈ N_{δ}(w), and there exists a cluster T_{i} ∈ T

Proof of Lemma 8-1

that includes N_{δ}(w). The route chosen for v, w will use the VPL^{1-m} in T_{i} by going from v to the root of the VPL^{1-m} (using a shortest route) and from there to w; denote the total length of it by X. This route is composed of no more than h VPs. Note that the distance to the center in N_{δ}(w) is no more than δ, and by Property 2 of T we have:

X ≤ 2Rad(T ) ≤ 2(2k − 1)Rad(C) = 2(2k − 1)δ < 4kδ

24 Proof of Lemma 8-2 Now suppose that d_{G}(v, w) ≥ \frac{δ}{2}, then the stretch factor satisfies μ ≤

\frac{4kδ}{δ/2} = 8k.

Proof of Lemma 8 □

Lemma 9 Let Ψ be the VPL^{m-m} produced by algorithm general_vpl. Then, its maximum load satisfies

L(Ψ) = O(khN^{\frac{1}{k} + \frac{2}{h}})

Proof of Lemma 9 By Theorem 2, each node is shared by at most Δ(T ) =

Proof of Lemma 9-1

O(k |C|^{1/k}) clusters. On the other hand, using Lemma 7, the load on a node caused by a single VPL^{1-m} is L(Ψ^{1−m}) ≤ \frac{h}{2}N^{2/h}, and since |C| ≤ N we get

L(Ψ) = O(hN^{\frac{2}{h}} kN^{\frac{1}{k}}) = O(khN^{\frac{1}{k} + \frac{2}{h}})

Proof of Lemma 9 □

So far, we have assumed that the distance between v and w is not less

Proof of Lemma 9-2

than \frac{δ}{2}. To achieve this, we apply the entire scheme for increasing values of δ. We start with δ = 2 and at the ith round take δ = 2^{i}. Clearly, this process completes in log_{2} N rounds. To ensure that the assumption used for the calculation of the stretch factor holds, we choose the VPL^{1-m} to connect v and w in the smallest cluster that includes both nodes. If we take δ = 2^{i} for an i that satisfies 2^{i−1} ≤ d(v, w) ≤ 2^{i}, then we have \frac{δ}{2} ≤ d(v, w) as assumed earlier. This process multiplies the load by a factor of log_{2} N, so we have

L(Ψ) = O(kh log NN^{\frac{1}{k} + \frac{2}{h}})

The following theorem summarizes the characteristics of the above description:

Theorem 3 Given an arbitrary network G with N nodes, and k, h > 1, the above scheme yields an h-feasible VPL^{m-m} with stretch factor μ ≤ 8k and load L(Ψ) = O(kh log NN^{\frac{1}{k} + \frac{2}{h}}).

25

Gerstel, Cidon, Zaks Optimal Virtual Path Layout in ATM §A.1

6 Summary

In this paper we presented a model and a class of problems for designing the

6-1

layout of virtual paths in a given ATM network to be used for general-purpose connection routing. We first defined the characteristics that are important for such a layout, the VPL^{m-m} problem, and the simpler VPL^{1-m} problem. Next, we showed that both problems are NP-complete, but presented an optimal construction scheme for a more limited variant of the VPL^{1-m} (namely, with stretch factor μ = 1 and assuming a tree network). We then demonstrated how this limited problem can serve as a building block for a suboptimal solution of a VPL^{m-m} (in which μ > 1).

We believe that our approach quite accurately models certain routing

6-2

problems in ATM networks, including the optimality criterion. We expect this work to motivate further work in finding better schemes for general networks, in extending the existing schemes for supporting fault tolerance in the network, and in extending the characteristics of a good layout to the case when some statistics regarding the volume and bandwidth of connections between every pair of nodes is known.

7 Acknowledgment

We would like to thank the managing editor of this journal, Mike O’Donnell, and the copy editor, Lisa Clark, for their very thorough and involved work in improving the presentation of this paper.

A Appendix

A.1 NP-Completeness Result for the VPL^{1-m} Problem

Recalling the problem statement in Section 4, we now prove that the OPT-

A.1-1

VPL^{1-m} problem is NP-complete (if the stretch factor is unbounded).

Theorem 4 OPT-VPL^{1-m} is NP-complete.

Proof of Theorem 4 Clearly OPT-VPL^{1-m} is in NP. To show NP-

Proof of Theorem 4-1

completeness, we reduce it to:

Problem: The disjoint connecting paths problem (ND40) [GJ79]. 26

= =

v

c_{v}

v

A limiter λ_{p}(v)

p
p−1 b_{1}^{v}...b_{n−3}^{v}
a_{1}

a_{p}

p

v w

v

w

b_{1}^{a1}

b_{n−2}^{a1}

b_{n−2}^{ap}

An extender ε_{p}(v, w)

b_{1}^{ap}
a_{2}
b_{1}^{a2}

b_{n−2}^{a2}

Figure 6: The limiter and extender components

Instance: An undirected graph G = (V, E), collection of disjoint pairs of nodes (s_{1}, t_{1}), (s_{2}, t_{2}), …, (s_{k}, t_{k}).

Question: Does G contain k mutually node-disjoint paths, one connecting s_{i} and t_{i} for each i ∈ {1, …, k}?

Given an instance of ND40, let n = |V |. Define the following components (see Figure 6):

Extender (ε_{p}(v, w)): This component extends a path that goes through v and w in V to include p additional hops. It is composed of a path of p nodes a_{1}, …, a_{p}, each of which is connected to n − 2 new nodes b_{1}^{a_{i}}, …, b_{n−2}^{a_{i}}. In addition, v is connected to a_{1} and w to a_{p}. In the case when p = 0, the extender reduces to an edge (v, w).

Limiter (λ_{p}(v)): This component limits the path from its head v to the root, to include no more than h − p hops. It also limits the number of VPs that may go through v. The limiter is constructed by connecting n − 3 new nodes (b_{1}^{v}, …, b_{n−3}^{v}) to v, adding yet another new node c_{v}, and connecting v and c_{v} by ε_{p−1}(v, c_{v}).

Let U = V \ {t_{1}, t_{2}, …, t_{k}}, let L = n, and h = k + 2. Consider the following transformation of G to G′ (see Figure 7, in which the extender is drawn as a rectangle and the limiter as a triangle):

27 • Initially define G′ as G.

• Add a new node r to G′.

• Add a limiter λ_{1}(v) to every node v ∈ U.

• Add an extender ε_{h−1}(v, r) for every node v ∈ U.

• Add an extender ε_{h−i+1}(s_{i}, r) to every s_{i}, i ∈ {1, …, k}.

• Add a limiter λ_{i}(t_{i}) to every t_{i}, i ∈ {1, …, k}.

• Add a node d_{i} and an edge (d_{i}, t_{i}) to every t_{i}, i ∈ {1, …, k}. We prove that OPT-VPL^{1-m} replies True on G′ with r as the root iff

Proof of Theorem 4-2

ND40 replies True on G. In the proofs we use the following terminology: • A node v with L(v) = L is called saturated.

• A route from v to r is said to go via a node y if the route includes two VPs that are concatenated in y.

• A route from v to r is said to go through y if y is included in one of the VPs that form the route.

• In a minimal VPL, the (single) VP that starts at a node v and is used

(as a first VP) in the path to r is called the VP from v. Lemma 10 The limiter and extender have the following properties:

1. Given a node v with a limiter λ_{p}(v), the route from v to r is no more than h − p hops.

2. Given a node v with a limiter λ_{p}(v), then the VPs that include v are from v itself and from its limiter, plus at most one additional VP.

3. Given two nodes v, w with a limiter λ_{q}(v) and an extender ε_{p}(v, w), then a route through v and w includes at least p − 1 complete VPs (excluding the VPs that go through v and w).

Proof of Lemma 10 We divide the proof into the three cases:

Gerstel, Cidon, Zaks Optimal Virtual Path Layout in ATM §A.1

h−1  ^{h−1}  ^{h−2}  ^{h−1}  ^{h−3}  ^{1}  ^{h−1} 1  2  h − 2 1 v  1  1 r d_{1}  t_{1}  d_{2}  t_{2}  d_{k}  t_{k} s_{1}  s_{2}  s_{k} 1

Figure 7: The transformed graph G′ 29

Chicago Journal of Theoretical Computer Science 1996-3 Case 1 Since c_{v} is connected to a node a_{1} of an extender in λ_{p}(v), its VP can either end at a_{1} or continue (toward v). If it continues, then the VP from a_{1} must also go through a_{2} (there is no other way to connect r), and L(a_{2}) > L. Therefore it stops at a_{1}. From similar considerations, the VP from a_{2} stops at a_{3} and finally, the VP from a_{p} stops at v, otherwise, there are two VPs that must go through some node u ∈ U and hence more than k VPs that go through some s_{i}, causing L(s_{i}) > L for some s_{i}. Therefore, v must connect r using h − p hops or less (the case when p = 1 is trivial).

Case 2 Every VP from b_{v} in λ_{p}(v) goes through v, plus one VP from v and one from a_{p}, a total of L−3+1+1 = L−1, leaving one extra VP through v.

Case 3 The proof resembles the one of Case 1, with the difference that the VP from a_{1} does not go through v because if it does, v is saturated, and no other VP can go through v.

Proof of Lemma 10 □

Proof of Theorem 4-3

Proposition 1 In every VPL^{1-m} on G′, the load on every node v ∈ U is composed of one VP from v, one VP that includes v from the L − 2 nodes in ε_{1}(v), and no more than one additional VP, which we term the extra VP of v. In every t_{f}i, the load is composed of the same VPs and one VP from d_{i}, hence with no extra VP.

Lemma 11 If there exists a solution for OPT-VPL^{1-m} on G′, then there are k disjoint paths in G between every s_{i} and t_{i}.

Proof of Lemma 11 By the previous Lemma, the route from t_{k} includes

Proof of Lemma 11-1

no more than two VPs. This route cannot go through any ε_{h−1}(v, r), and it cannot go through s_{i}, i ≠ k because of the ε_{h−i+1}(s_{i}, r) which adds at least k + 2 − (k + 1) + 1 − 1 = 1 VPs in the route from s_{i} to r (by Lemma 10), excluding the VP to r and the VP from t_{k} through s_{i} (a total of three VPs). Therefore, the route from t_{k} goes through s_{k}.

From similar considerations, the route from t_{k−1} cannot go through s_{i},

Proof of Lemma 11-2

for i < k − 1. Also, it cannot go through s_{k}, since the extra VP of s_{k} was used by the route from t_{k}. And by repeating this argument, the route from t_{i} goes through s_{i}. Note that this route is composed of a single VP (that

30 includes both t_{i} and s_{i}), because λ_{i}(t_{i}) and ε_{h−i+1}(s_{i}, r) use h − 1 VPs. Also note that each of these paths is node disjoint (since every intermediate node has only one extra VP), and that a path from t_{i} does not go through t_{j}, since every t_{j} is already saturated (because of d_{j}).

Proof of Lemma 11 □

Lemma 12 If there are k disjoint paths between s_{i} and t_{i} respectively, then there exists a solution for OPT-VPL^{1-m} on G′ with L = n, h = k + 2. Proof of Lemma 12 Build a VPL^{1-m} in the following manner:

• Create a VP between every b_{i}^{v} and v.

• Create a VP between every v ∈ U to a_{1} in ε_{h−1}(v, r), and a VP between every a_{p} in ε_{p}(x, r) to r (for every x for which such an extender exists).

• Connect c_{v} to a_{1} of the extender in every λ_{p}(v) by a VP, and a_{p} to v.

• Create a VP between every a_{i} to a_{i+1} in every extender (if p = 0 in ε_{p}(u, v) then connect u and v by a VP).

• Connect d_{i} to t_{i} for every i ∈ {1, …, k}.

• Connect every t_{i} to a_{1} in ε_{p}(s_{i}, r) using the path obtained by ND40

through s_{i} (as indicated by the dotted lines in Figure 7). It is easy to verify that L(Ψ) ≤ L.

Proof of Lemma 12 □

By Lemma 11, if there exists a VPL^{1-m} on G′, then there exist k disjoint

Proof of Theorem 4-4

paths from s_{i} to t_{i} in G. By Lemma 12, if there are k such paths, then there is a VPL^{1-m} on G′, hence our transformation is correct.

Proof of Theorem 4 □

A.2 NP-Completeness Result for the VPL^{m-m} Problem

The proof that the VPL^{m-m} problem is NP-complete is based on the following

A.2-1

NP-complete problem.

Problem: The Symmetric Forwarding Index Problem (SFI) [Saa93].

Instance: An undirected graph G = (V, E), an integer k > 0.

Question: Does there exist a set R of \binom{|V |}{2} undirected paths in G such that for every pair x, y ∈ V there exists a path in R whose endpoints are x and y, and the number of paths in R that go through any node v, for which v is not an endpoint, does not exceed k?

The VPL^{m-m} problem is formalized as the following decision problem.

A.2-2

Problem: The optimal h-hop VPL^{m-m} problem (OPT-VPL^{m-m}(h)).

Instance: An undirected graph G = (V, E), an integer L > 0.

Question: Assuming μ = ∞, does there exist an h-feasible VPL^{m-m}, Ψ, on G such that L(Ψ) ≤ L?

We first reduce the OPT-VPL^{m-m} (1) problem to SFI, and then reduce

A.2-3

OPT-VPL^{m-m} (h + 2) to OPT-VPL^{m-m} (h) for every h, by this proving that OPT-VPL^{m-m}(h) is NP-complete for every odd h. A proof that OPT-VPL^{m-m}(2) is NP-complete would suffice to extend this result to every h > 0.

Lemma 13 OPT-VPL^{m-m}(1) is NP-complete.

Proof of Lemma 13 Given an instance of SFI, we define an instance of OPT-VPL^{m-m} (1) with the same graph G and L = k + |V | − 1. This proof is simple, since the only difference between the problems is that in SFI a path is not considered part of the “load” on the endpoint nodes, while in OPT-VPL^{m-m}(1) it is considered as part of the load. However, since there are n − 1 paths in R for which a given node is an endpoint, the load limit must be increased by |V | − 1.

Proof of Lemma 13 □

Lemma 14 OPT-VPL^{m-m}(h + 2) is NP-complete if OPT-VPL^{m-m}(h) is NP-complete.

32 Proof of Lemma 14 Let a graph G = (V, E) and L > 0 be an instance of

Proof of Lemma 14-1

OPT-VPL^{m-m} (h), with |V | = n. Construct a graph G′ = (V′, E′) by initially taking G′ as G and then connecting M = nL new nodes {w_{v}^{i}}_{i=1}^{M} to every node v ∈ V.

We show that there exists a solution Ψ to OPT-VPL^{m-m}(h) on G with

Proof of Lemma 14-2

load L(Ψ) ≤ L iff there is a solution Ψ′ to OPT-VPL^{m-m}(h + 2) on G′ with load L(Ψ) ≤ L′ = L + M. Assume Ψ is a solution Ψ to OPT-VPL^{m-m}(h), and add VPs from every w_{v}^{i} to v. The resulting VPL Ψ′ is a solution to OPT-VPL^{m-m} (h + 2) since the distance in Ψ between every pair of nodes a, b ∈ V satisfies H_{μ}(a, b) ≤ h, and therefore the distance in Ψ′ between every w_{a}^{i} and w_{b}^{j} obeys H_{μ}(w_{a}^{i}, w_{b}^{j}) ≤ h + 2, and H_{μ}(a, w_{b}^{i}) ≤ h + 1. Since the load in Ψ is bounded by L at each node, the load in Ψ′ is clearly bounded by L′.

On the other hand, if there exists a solution Ψ′ to OPT-VPL^{m-m}(h + 2)

Proof of Lemma 14-3

on G′ then two cases are possible:

Proof of Lemma 14-4 Case 1 For every a, b ∈ V in Ψ′ H_{μ}(a, b) ≤ h. In this case, we may take the VPs whose endpoints are in V as a solution Ψ to the OPT-VPL^{m-m}(h) problem. It is clear that Ψ uses only nodes from G (a simple path from a to b cannot include any w_{x}^{i}), and that the solution is h-feasible. To show that L(Ψ) ≤ L, note that each node in x ∈ V has at least load M from its neighbors w_{x}^{i}. This leaves only L for VPs between nodes in V.

Case 2 Otherwise, there exists a pair of nodes a, b ∈ V for which

Proof of Lemma 14-5

H_{μ}(a, b) > h in Ψ′. Regard the sets of nodes W_{a} = { w_{a} | 1 ≤ i ≤ M } and W_{b} = { w_{b}^{i} | 1 ≤ i ≤ M }. If there exists a pair of nodes x_{a} ∈ W_{a}, x_{b} ∈ W_{b} which are included only in the VPs (x_{a}, a), (x_{b}, b) ∈ E_{Ψ}, then the path between x_{a} and x_{b} must include the path between a and b, and hence H_{μ}(x_{a}, x_{b}) = H_{μ}(a, b) + 2 > h + 2—a contradiction. For this reason, either all nodes in W_{a} or all nodes in W_{b} (without loss of generality, assume it is W_{a}) are included in VPs that include also a neighbor of a. By the pigeonhole principle, there exists some neighbor c ∈ V that is included in at least \frac{M}{n} such VPs. Now, since every node w_{c}^{j} adds to the load on c as well, we get L(c) ≥ M + \frac{M}{n} > M + L = L′—a contradiction.

Note that if there exists a VP (w_{a}^{i}, w_{c}^{j}) in Ψ′, which is considered in the

Proof of Lemma 14-6

second component of the above sum (i.e., as a VP from w_{c}^{j}), there must be another VP from w_{c}^{j} that contributes to the first component of this sum as

Gerstel, Cidon, Zaks Optimal Virtual Path Layout in ATM (Ref)

33 well, since (w_{a}^{i}, w_{c}^{j}) is part of the path from w_{a}^{i} to some node x_{b} in W_{b}.

Proof of Lemma 14 □

Theorem 5 OPT-VPL^{m-m} (h) is NP-complete for every odd h > 0.

Proof of Theorem 5 The proof follows directly from the previous two lemmata by induction on h.

Proof of Theorem 5 □

Acknowledgement of support: Part of Ornan Gerstel’s work was done while he was with the Computer Science Department, Technion, Haifa 32000, Israel. Part of Israel Cidon’s work was done while he was with Sun Microsystems Labs, 2550 Garcia Avenue, Mountain View, CA 94043.

References

[ABLP89] B. Awerbuch, A. Bar-Noy, N. Linial, and D. Peleg. Compact distributed data structures for adaptive routing. In 21st Symposium on Theory of Computing, pages 479–489, 1989.

[ACG^{+}90] B. Awerbuch, I. Cidon, I. Gopal, M. Kaplan, and S. Kutten. Distributed control for PARIS. In 9th Annual ACM Symposium on Principles of Distributed Computing, pages 145–160, 1990.

[AP92] B. Awerbuch and D. Peleg. Routing with polynomial communication-space tradeoff. SIAM Journal on Discrete Math, 5(2):151–162, May 1992.

[ATTD94] S. Ahn, R. P. Tsang, S. R. Tong, and D. H. C. Du. Virtual path layout design on ATM networks. In IEEE Infocom ’94, pages 192–200, 1994.

[CG88] I. Cidon and I. Gopal. PARIS: An approach to integrated highspeed networks. International Journal of Digital and Analog Cabled Systems, 1(2):77–86, April–June 1988.

34 [CGG^{+}92] I. Cidon, I. Gopal, P. M. Gopal, J. Janniello, and M. Kaplan. The

plaNET/ORBIT high speed network. IBM Research Report RC 18270, IBM Research Division, Watson Research Center, August 1992.

[CGZ94] I. Cidon, O. Gerstel, and S. Zaks. A scalable approach to routing in ATM networks. In G. Tel and P. M. B. Vitányi, editors, The 8th International Workshop on Distributed Algorithms (LNCS 857), pages 209–222, Terschelling, The Netherlands, October 1994. Springer-Verlag. To appear in IEEE/ACM Transactions on Networking.

[CS94] R. Cohen and A. Segall. Connection management and rerouting in ATM networks. In IEEE Infocom’94, pages 184–191, 1994.

[Eve79] S. Even. Graph Algorithms. Computer Science Press, 1979.

[FJ86] G. N. Frederickson and R. Janardan. Separator-based strategies for efficient message routing. In 27th Symposium on Foundations of Computer Science, pages 428–437, 1986.

[FJ88] G. N. Frederickson and R. Janardan. Designing networks with compact routing tables. Algorithmica, 3:171–190, 1988.

[Ger95] O. Gerstel. Virtual Path Design in ATM Networks. PhD thesis, Technion, Israel Institute of Technology, December 1995.

[GJ79] M. R. Garey and D. S Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co., 1979.

[GZ94] O. Gerstel and S. Zaks. The virtual path layout problem in fast networks. In The 13th Annual ACM Symposium on Principles of Distributed Computing, pages 235–243, Los Angeles, CA, August 1994.

[HH91] R. Händler and M. N. Huber. Integrated Broadband Networks: An Introduction to ATM-Based Networks. Addison-Wesley, 1991.

[HKIT94] H. Hadama, R. Kawamura, T. Izaki, and I. Tokizawa. Direct virtual path configuration in large-scale ATM networks. In IEEE Infocom’94, pages 201–207, 1994.

35 [ITU90] ITU recommendation. I series (B-ISDN), Blue Book, November

1990.

[KK77] L. Kleinrock and F. Kamoun. Hierarchical routing for large networks; preformance evaluation and optimization. Computer Networks, 1:155–174, 1977.

[KK80] L. Kleinrock and F. Kamoun. Optimal clustering structures for hierarchical topological design of large computer networks. Networks, 10:221–248, 1980.

[LB92] J. Y. Le Boudec. The asynchronous transfer mode: a tutorial. Computer Networks and ISDN Systems, 24:279–309, 1992.

[LPS91] T. F. La Porta and M. Schwarz. Architectures, features, and implementation of high-speed transport protocols. IEEE Communications Magazine, pages 14–22, May 1991.

[PU88] D. Peleg and E. Upfal. A tradeoff between space and efficiency for routing tables. In 20th Symposium on Theory of Computing, pages 43–52, 1988.

[Saa93] R. Saad. Complexity of the forwarding index problem. SIAM Journal on Discrete Math, 6(3):418–427, 1993.

[SK85] N. Santoro and R. Khatib. Labelling and implicit routing in networks. The Computer Journal, 28:5–8, 1985.

36