Institute for Systems Research Technical Reports

Permanent URI for this collectionhttp://hdl.handle.net/1903/4376

This archive contains a collection of reports generated by the faculty and students of the Institute for Systems Research (ISR), a permanent, interdisciplinary research unit in the A. James Clark School of Engineering at the University of Maryland. ISR-based projects are conducted through partnerships with industry and government, bringing together faculty and students from multiple academic departments and colleges across the university.

Browse

Subject: search.filters.subject.communication networks

Search Results

Now showing 1 - 5 of 5
  • Thumbnail Image
    Item
    Convergence Results for Ant Routing Algorithms via Stochastic Approximations
    (2009-10) Purkayastha, Punyaslok; Baras, John; Baras, John
    In this paper, we provide convergence results for an Ant-Based Routing (ARA) Algorithm for wireline, packet-switched communication networks, that are acyclic. Such algorithms are inspired by the foraging behavior of ants in nature. We consider an ARA algorithm proposed by Bean and Costa. The algorithm has the virtues of being adaptive and distributed, and can provide a multipath routing solution. We consider a scenario where there are multiple incoming data traffic streams that are to be routed to their respective destinations via the network. Ant packets, which are nothing but probe packets, are introduced to estimate the path delays in the network. The node routing tables, which consist of routing probabilities for the outgoing links, are updated based on these delay estimates. In contrast to the available analytical studies in the literature, the link delays in our model are stochastic, time-varying, and dependent on the link traffic. The evolution of the delay estimates and the routing probabilities are described by a set of stochastic iterative equations. In doing so, we take into account the distributed and asynchronous nature of the algorithm operation. Using methods from the theory of stochastic approximations, we show that the evolution of the delay estimates can be closely tracked by a deterministic ODE (Ordinary Differential Equation) system, when the step-size of the delay estimation scheme is small. We study the equilibrium behavior of the ODE system in order to obtain the equilibrium behavior of the routing algorithm. We also explore properties of the equilibrium routing probabilities, and provide illustrative simulation results.
  • Thumbnail Image
    Item
    Convergence Results for Ant Routing Algorithms via Stochastic Approximation and Optimization
    (2007) Purkayastha, Punyaslok; Baras, John S.
    ``Ant algorithms'' have been proposed to solve a variety of problems arising in optimization and distributed control. They form a subset of the larger class of ``Swarm Intelligence'' algorithms. The central idea is that a "swarm" of relatively simple agents can interact through simple mechanisms and collectively solve complex problems. Instances that exemplify the above idea abound in nature. The abilities of ant colonies to collectively accomplish complex tasks have served as sources of inspiration for the design of ``Ant algorithms''. Examples of ``Ant algorithms'' are the set of ``Ant Routing'' algorithms that have been proposed for communication networks. We analyze in this paper Ant Routing Algorithms for packet-switched wireline networks. The algorithm retains most of the salient and attractive features of Ant Routing Algorithms. The scheme is a multiple path probabilistic routing scheme, that is fully adaptive and distributed. Using methods from adaptive algorithms and stochastic approximation, we show that the evolution of the link delay estimates can be closely tracked by a deterministic ODE system. A study of the equilibrium points of the ODE gives us the equilibrium behavior of the routing algorithm, in particular, the equilibrium routing probabilities, and mean delays in the links under equilibrium. We also show that the fixed-point equations that the equilibrium routing probabilities satisfy are actually the necessary and sufficient conditions of an appropriate optimization problem. Simulations supporting the analytical results are provided.
  • Thumbnail Image
    Item
    Performance Evaluation in Multi-Rate, Multi-Hop Communication Networks with Adaptive Routing
    (1998) Liu, Mingyan D.; Baras, John S.; Misra, Archan; ISR; CSHCN
    Accurate performance evaluation has always been an important issue in network design and analysis. Discrete event simulation has been known to be accurate but very time consuming. A particular performance metric of interest is the end-to-end blocking probability in a circuit-switched loss network. Various analytical approaches and approximation schemes have been suggested and among them, the fixed-point method, or reduced load method, has been receiving much attention. However, most of these schemes either consider only single traffic rate situations or multi-rate traffic under fixed routing. We develop an approximation scheme to estimate end-to-end blocking probability in a multi-rate multi-hop network with an adaptive routing scheme. The approximation results are compared with that of discrete event simulation. An example of application is also provided in which the proposed scheme is linked to the optimization tool CONSOL-OPTCAD to get network design trade-offs. This paper was presented at the "ATIRP ARL Federal Laboratory 2nd Annual Conference," February 5-6, 1998, University of Maryland, College Park campus.
  • Thumbnail Image
    Item
    The Acts Experiments program at the Center for Satellite and Hybrid Communication Networks
    (1997) Friedman, Daniel E.; Gupta, Sonjai K.; Zhang, C.; Ephremides, Anthony; ISR; CSHCN
    This paper describes experiments conducted over ACTS and the associated T1~VSAT terminal. The experiments were motivated by the commercial potential of low-cost receive-only satellite terminals that can operate in a hybrid network environment, and by the desire to demonstrate frame relay technology over satellite networks. The first experiment tested highly adaptive methods of satellite bandwidth allocation in an integrated voice- data service environment. The second involved comparison of FEC and ARQ methods of error control for satellite communication with emphasis on the advantage that a hybrid architecture provides, especially in the case of multicasts. Finally, the third experiment demonstrated hybrid access to databases through the use of Mosaic and compared the performance of internetworking protocols for interconnecting LANs via satellite. A custom unit termed Frame Relay Access Switch (FRACS) was developed by COMSAT Laboratories for these experiments; the preparation and conduct of these experiments involved a total of twenty people from the University of Maryland, the University of Colorado, and COMSAT Laboratories, from late 1992 through 1995.
  • Thumbnail Image
    Item
    Markov Decision Models with Weighted Discounted Criteria
    (1991) Feinberg, Eugene A.; Shwartz, Adam; ISR
    We consider a discrete time Markov Decision Process with infinite horizon. The criterion to be maximized is the sum of a number of standard discounted rewards, each with a different discount factor. Situations in which such criteria arise include modeling investments, modeling projects of different durations and systems with different time-scales, and some axiomatic formulations of multi-attribute preference theory. We show that for this criterion for some positive e there need not exist an e - optimal (randomized) stationary strategy, even when the state and action sets are finite. However, e - optimal Markov (non-randomized) strategies and optimal Markov strategies exist under weak conditions. We exhibit e - optimal Markov strategies which are stationary from some time onward. When both state and action spaces are finite, there exists an optimal Markov strategy with this property. We provide an explicit algorithm for the computation of such strategies.