Institute for Systems Research

In this thesis we describe our work onthe development of connection level mathematical models used forestimating network performance characteristics such as throughput,delay and blocking probability. The type of models we use andinvestigate are of the "Loss Network" type, which have been usedwidely in legacy telephone networks and in cellular networks forestimating "availability".

These network models can also be used inestimating performance in general packet-switched networks usingeffective bandwidth concepts. In particular, these models are directlyapplicable in studying connection blocking for networks using QoSrouting schemes.

Computational complexity is a serioususability bottleneck for such algorithms. We describe fast (twoto three orders of magnitude faster than discrete event simulation)approximation algorithms we have developed for accurately estimatingblocking probability in a random topology network, using state-dependentrouting, with multiple classes of traffic. We describe even fasteralgorithms based on a hierarchical loss network model we have developed.The latter are well matched to networks that have a natural hierarchicalarchitecture, or which use some form of hierarchical routing to furtherreduce computational cost. We also developed models for networks usingdelay-based QoS routing.

An important objective of our work is todemonstrate the utility of these models for effective design anddimensioning of a large network so that a certain set of QoS requirementsare met. We show how typical design and dimensioning problems can beformulated as a multi-objective constrained optimization problem, usingperformance estimation network models; an approach that leads naturallyto very useful trade-off analysis. We describe our research in thedevelopment of a general network design and dimensioning methodology bylinking our performance models with Automatic Differentiation andmulti-objective optimization algorithms and tools. We presentexamples and applications that demonstrate the speed and versatility ofour methodology and algorithms.

As networks grow in size, nodes tendto form clusters geographically and hierarchical routing schemes are morecommonly used, and it is important that network modeling methods havescale-up capabilities. Loss networks and reduced load/fixed point modelsare often used toapproximate call blocking probabilities and hence throughput in a circuitswitched network. We use the same idea for estimating connection blockingin a data network with certain QoS routing schemes. However so far most workbeing done in this area is for flat networks with flat routing schemes.

We aim at developing a more efficient approximation method for networksthat have a natural hierarchy and/or when some form of hierarchical routingpolicy is used. We present hierarchical models in detail for fixedhierarchical routing and dynamic hierarchical routing policies,respectively, viathe notion of network abstraction, route segmentation, traffic segregationand aggregation. Computation is done separately within each cluster (local)and among clusters (global), and the fixed point is obtained by iterationbetween local and global computations. We present results from bothnumerical experiments and discrete event simulations.

As networks grow in size, nodes tendto form clusters geographically and hierarchical routing schemes are morecommonly used. Loss network and reduced load models are often used toapproximate end-to-endcall blocking probabilities, and hence, throughput. However so far all workbeing done in this area is for flat networks with flat routing schemes.

We aim at developing a more efficient approximation method for networksthat have a natural hierarchy and/or when some form of hierarchical routingpolicy is used. We present two hierarchical models in detail for fixedhierarchical routing and dynamic hierarchical routing policies,respectively, via the notion of network abstraction, route segmentation, traffic segregationand aggregation. Computation is done separately within each cluster (local)and among clusters (global), and the fixed point is obtained by iterationbetween local and global computations. We also present numerical resultsfor the first case.

However, there are certain performance problems withproviding Internet over satellite due to the nature of TCP/IP protocol suite and the satellite link characteristics. In this paper, we describe a simulation study of an architecture for improving the performance of TCP/IP over satellite links.

On each end of the satellite link, there are gateways that split the TCP connection so that the satellite link is transparent to the end hosts.

The split TCP connection over the satellite segment is then optimized.TCP congestion control is maintained on each segment of the split connection.

We simulated such an architecture in OPNET and present results showing improved throughput over the satellite link.

We propose a fixed-point method, a.k.a. reduced load approximation,to estimate the end-to-end blocking probability for such networks.The approximation scheme is shownto be asymptotically correct in a natural limiting regime, and it givesconservative estimates of blocking probabilities under heavy trafficload.

Simulation results are provided to compare performance estimatesobtained from our analytical approximation scheme and discrete eventsimulations.

We also show how this analytical approximation scheme can be linked withnumerical mathematical programming tools to help design a network,by selecting network design parameters via trade-off analysis, evenwith several design objectives.

In one application we use the multi-objective optimization toolCONSOL-OPTCAD to design trunk reservation parameters and balance linkcapacity. In another application we use automatic differentiationto get sensitivities of blocking probabilities w.r.t. offered trafficload.

The performance metric of interest is the end-to-end call blockingprobability. Blocking probabilities in a loss network have been studiedquite extensively but very few considered multiple traffic classes andrates together with adaptive/state dependent routing.

We propose a fixed-point method, a.k.a. reduced load approximation,to estimate the end-to-end blocking probability in a multihop, multirateloss network with adaptive routing. Simulation results are provided tocompare with that of approximations. The approximation scheme is shownto be asymptotically correct in a natural limiting regime, and it givesconservative estimates of blocking probabilities under heavy trafficload.

This paper has been published in the Proceedings of 2nd Annual ATIRP Conference(ATIRP'99).

Unicast tunnels are used as tree links to connect neighbors on theuser-multicast tree. Thus, AMRoute does not need to besupported by network nodes that are not interested/capable ofmulticast, and group state cost is incurred only by group senders and receivers. Also, the use of tunnels as tree links implies that tree structure does not need to change even in case of a dynamic network topology, which reduces the signaling traffic and packet loss. Thus AMRoute does not need to track network dynamics; the underlying unicast protocol is solely responsible for this function.

AMRoute does not require a specific unicast routing protocol; therefore, it can operate seamlessly over separate domains with different unicast protocols.

Certain tree nodes are designated by AMRoute as logical cores, and are responsible for initiating and managing the signaling component of AMRoute, such as detection of group members and tree setup. Logical cores differ significantly from those in CBT and PIM-SM, since they are not a central point for data distribution and can migrate dynamically among member nodes.

Simulation results demonstrate that AMRoute signaling traffic and join latency remain at relatively low levels for typical group sizes. The results also indicate that group members receive a high proportion of data multicast by a sender, even in the case of a dynamic network.