You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format. However, this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the Department of Computer Science of the University of Maryland at College Park under terms that include this permission. All other rights are reserved by the author(s).
Numerical Evaluation of Hierarchical QoS Routing. Sungjoon Ahn. Gayathri Chittiappa. A. Udaya Shankar. May 1998.
We develop a numerical evaluation method for adaptive hierarchical QoS routing, and demonstrate its viability by application to two networks. Our approach models aggregation and delayed feedback in a straightforward way, and is scalable to the large networks needed to evaluate hierarchical routing. Department of Computer Science, University of Maryland,
Fast Evaluation of Ensemble Transients of Large IP Networks. Catalin T. Popescu. A. Udaya Shankar. May 11, 1998.
We extend a numerical approximate solution method (the Z-iteration) to time-dependent open networks of M(t)/M(t)/1/$\infty$ and M(t)/M(t)/1/K queues, and apply the method to obtain transient performance metrics of large IP networks. The method generates a set of coupled differential equations, one for each queue in the network. The equations are numerically unstable under certain conditions (e.g., large bandwidths and buffers), and we present techniques to overcome this problem. The resulting numerical procedure is accurate and very fast. For example, a 20-second evolution for a 1000-node network with high-speed links ($\approx 10^4$packets/sec) and large buffers ($\approx 10^4$packets) was obtained in 18 minutes on an Ultra Sparc, whereas simulation would take days. Department of Computer Science, University of Maryland,
Ibrahim Matta. A. Udaya Shankar. July 15, 1995.
Z-Iteration: Efficient Estimation of Instantaneous Measures. Multiple-class multiple-resource (MCMR) systems, where a class of customers requires a set of resources, are common. These systems are often analyzed under steady-state conditions. We describe a simple numerical-analytical method, referred to as Z-iteration, to estimate instantaneous (and steady-state) probability measures of time-dependent systems. The key idea is to approximate the relationship between certain instantaneous measures by the relationship between their steady-state counterparts, and use this approximation to solve dynamic flow equations. We show the generality of the Z-iteration by applying it to an integrated communication network, a parallel database server, and a distributed batch system. Validations against exact numerical solutions and discrete-event simulations show the accuracy and computational advantages of the Z-iteration. (Also cross-referenced as UMIACS-TR-94-116.1) University of Maryland Institute for Advanced Computer Studies, Dept. of Computer Science, Univ. of Maryland,
Cengiz Alaettinoglu. Ibrahim Matta. A. Udaya Shankar. A Scalable Virtual Circuit Routing Scheme for ATM Networks. October 1994.
High-speed networks, such as ATM networks, are expected to support diverse quality-of-service (QoS) requirements, including real-time QoS. Real-time QoS is required by many applications such as voice and video. To support such service, routing protocols based on the Virtual Circuit (VC) model have been proposed. However, these protocols do not scale well to large networks in terms of storage and communication overhead. In this paper, we present a scalable VC routing protocol. It is based on the recently proposed viewserver hierarchy, where each viewserver maintains a partial view of the network. By querying these viewservers, a source can obtain a merged view that contains a path to the destination. The source then sends a request packet over this path to setup a real-time VC through resource reservations. The request is blocked if the setup fails. We compare our protocol to a simple approach using simulation. Under this simple approach, a source maintains a full view of the network. In addition to the savings in storage, our results indicate that our protocol performs close to or better than the simple approach in terms of VC carried load and blocking probability over a wide range of real-time workload. (Also cross-referenced as UMIACS-TR-94-115) University of Maryland Institute for Advanced Computer Studies, Dept. of Computer Science, Univ. of Maryland,
Cengiz Alaettinoglu. A. Udaya Shankar. June 1994.
Hierarchical Inter-Domain Routing Protocol. Traditional inter-domain routing protocols based on superdomains maintain either ``strong'' or ``weak'' ToS and policy constraints for each visible superdomain. With strong constraints, a valid path may not be found even though one exists. With weak constraints, an invalid domain-level path may be treated as a valid path. We present an inter-domain routing protocol based on superdomains, which always finds a valid path if one exists. Both strong and weak constraints are maintained for each visible superdomain. If the strong constraints of the superdomains on a path are satisfied, then the path is valid. If only the weak constraints are satisfied for some superdomains on the path, the source uses a query protocol to obtain a more detailed ``internal'' view of these superdomains, and searches again for a valid path. Our protocol handles topology changes, including node/link failures that partition superdomains. Evaluation results indicate our protocol scales well to large internetworks. (Also cross-referenced as UMIACS-TR-94-73) University of Maryland Institute for Advanced Computer Studies, Dept. of Computer Science, Univ. of Maryland,
Ibrahim Matta. A. Udaya Shankar. May 1995.
Fast Time-Dependent Evaluation of Integrated Services Networks. We present a numerical-analytical method to evaluate integrated services networks with adaptive routing, scheduling and admission controls. We apply our method to connection-oriented networks supporting different types of real-time connections. The network dynamics is described by difference equations which can be solved for both transient and steady-state performances. Results indicate that our method is computationally much cheaper than discrete-event simulation, and yields accurate performance measures. We compare the performance of different routing schemes on the NSFNET backbone topology with a weighted fair-queueing link scheduling discipline and admission control based on bandwidth reservation. We show that the routing scheme that routes connections on paths which are both under-utilized and short (in number of hops) gives higher network throughput. (Also cross-referenced as UMIACS-TR-94-28) University of Maryland Institute for Advanced Computer Studies, Dept. of Computer Science, Univ. of Maryland,
Cengiz Alaettinoglu. A. Udaya Shankar. March 1995.
The Viewserver Hierarchy for Inter-Domain Routing:Protocols and Evaluation. We present an inter-domain routing protocol based on a new hierarchy, referred to as the viewserver hierarchy. The protocol satisfies policy and ToS constraints, adapts to dynamic topology changes including failures that partition domains, and scales well to large number of domains without losing detail (unlike the usual scaling technique of aggregating domains into superdomains). Domain-level views are maintained by special nodes called viewservers. Each viewserver maintains a view of a surrounding precinct. Viewservers are organized hierarchically. To obtain domain-level source routes, the views of one or more viewservers are merged (upto a maximum of twice the levels in the hierarchy). We also present a model for evaluating inter-domain routing protocols, and apply this model to compare our viewserver hierarchy against the simple approach where each node maintains a domain-level view of the entire internetwork. Our results indicate that the viewserver hierarchy finds many short valid paths and reduces the amount of memory requirement by two orders of magnitude. (Also cross-referenced as UMIACS-TR-93-98.1) University of Maryland Institute for Advanced Computer Studies, Dept. of Computer Science, Univ. of Maryland,
A. Udaya Shankar. David Lee. December 1994.
Minimum-Latency Transport Protocols with Modulo-N Incarnation Numbers. To provide reliable connection management, a transport protocol uses 3-way handshakes in which user incarnations are identified by bounded incarnation numbers from some modulo-$N$ space. Cacheing schemes have been proposed to reduce the 3-way handshake to a 2-way handshake, providing the minimum latency desired for transaction-oriented applications. In this paper, we define a class of cacheing protocols and determine the minimum $N$ and optimal cache residency time as a function of real-time constraints (e.g.\ message lifetime, incarnation creation rate, inactivity duration, etc.). The protocols use the client-server architecture and handle failures and recoveries. Both clients and servers generate incarnation numbers from a local counter (e.g.\ clock). These protocols assume a maximum duration for each incarnation; without this assumption, there is a very small probability ($\approx \frac{1}{N^2}$) of misinterpretation of incarnation numbers. This restriction can be overcome with some additional cacheing. (Also cross-referenced as UMIACS-TR-93-24.1) University of Maryland Institute for Advanced Computer Studies, Dept. of Computer Science, Univ. of Maryland,
Cengiz Alaettinoglu. A. Udaya Shankar. August 1993.
Stepwise Assertional Design of Distance-Vector Routing Algorithms. There are many kinds of distance-vector algorithms for adaptive routing in wide-area computer networks, ranging from the classical Distributed Bellman-Ford to several recent algorithms that have better performance. However, these algorithms have very complicated behaviors and their analyses in the literature has been incomplete (and operational). In this paper, we present a stepwise assertional design of a recently proposed distance-vector algorithm. Our design starts with the Distributed Bellman-Ford and goes through two intermediate algorithms. The properties established for each algorithm hold for the succeeding algorithms. The algorithms analyzed here are representative of various internetwork routing protocols. (Also cross-referenced as UMIACS-TR-92-39.1) University of Maryland Institute for Advanced Computer Studies, Dept. of Computer Science, Univ. of Maryland,
Last Generated Fri Aug 11 04:01:01 EDT 2000