Cowen gave a universal compact routing algorithm with a stretch factor of three and table-size of O(n2/3log4/3n) based on a simple and practical model. (The table-size is later improved to O(n1/2log3/2n).) This paper considers, using the same model, how the necessary table-size differs if the stretch factor must be less than three. It is shown that: (i) There is a routing algorithm with a stretch factor of two whose table-size is (n -+ 2)log n. (ii) There is a network for which any routing algorithm that follows the model and with a stretch factor of less than three needs a table-size of (n - 2)log n in at least one node. Thus, we can only reduce roughly an additive log n (i.e., table-entries) from the trivial table-size of n log n which obviously enables shortest-path routing. Furthermore it turns out that we can reduce only an additive log n (i.e., only one table-entry) from the trivial n log n if we have to achieve a stretch factor of less than two. Thus the algorithm (i) is (roughly) tight both in its stretch factor and in its table-size.

Fast packet switches for variable-size packets have become an everyday necessity with the rapid growth in the volume of Internet traffic. Such switches can be designed in two different ways, either by segmenting packets into smaller fixed-size cells and designing packet switches for such cells, or by designing generic packet switches for variable-size packets, where packet segmentation and reassembly can be omitted. The second option is investigated in this paper. The synchronous operation mode with time-limited bulk service is selected. The switching fabric is assumed to be internally non-blocking and provided with input queues. A previous maximum switch throughput analysis has been done under the assumption that the length of the time slot is fixed set to its minimum allowed value (Tmin). In this work, a so-called time-slot stretch factor (SF) is introduced. The actual time-slot length is determined by multiplying Tmin with the SF, where SF. Next, a so-called Internet traffic-source model is proposed based on findings from real IP traffic measurements. The performance implications of the proposed time-slot length modification are analyzed by discrete-event computer simulation. The maximum switch throughput is increased by increasing the SF value, e.g. for uniform packet size distribution and SF=10, the maximum switch throughput is increased from 75% to 97%. The influence of the traffic-source characteristics on the maximum switch throughput is decreased when SF value is increased. In order to prevent any possible throughput degradations, it is advisable to use integer SF values. Packet delay analysis has revealed that by increasing the SF value, the mean packet delay is also increased. Nevertheless, it is shown that the number of switch input and output ports is the most important factor to be considered when packet delay is at stake. Service class differentiation inside investigated packet switch is possible and is not affected by the increasing SF value. Such a packet switch is suitable for implementation in wide area networks, due to high transmission speeds and the small number of switch ports.