We study connection networks in which certain pairs of nodes have to be con
nected by k edge-disjoint paths, and study bounds for the minimal sum of le
ngths of such k paths. We define the related notions of total(k)-distance f
or a pair of nodes and total(k)-diameter of a connection network, and study
the value TDk(d) which is the maximal such totalk-diameter of a network wi
th diameter d. These notions have applications in fault-tolerant routing pr
oblems, in ATM networks, and in compact routing in networks. We prove an up
per bound on TDk(d) and a lower bound on the growth of TDk(d) as functions
of k and d; those bounds are tight, theta(d(k)), when k is fixed. Specifica
lly, we prove that TDk(d) less than or equal to 2(k-1)d(k), with the except
ions TD2(1) = 3, TD3(1) = 5, and that for every k, d(0) > 0, there exists (
a) an integer d greater than or equal to d(0) such that TDk(d) greater than
or equal to d(k)/k(k), and (b) a k-connected simple graph G with diameter
d such that d greater than or equal to d(0), and whose total(k)-diameter is
at least (d - 2)(k)/k(k). (C) 2000 Elsevier Science B.V. All rights reserv
ed.