Technical Reports from UMIACS

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

Browse

Filter results by typing the first few letters
Now showing 1 - 4 of 4
  • Thumbnail Image
    Item
    Hierarchical Inter-Domain Routing Protocol with On-Demand ToS and Policy Resolution
    (1998-10-15) Alaettinoglu, Cengiz; Shankar, A. Udaya
    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)
  • Thumbnail Image
    Item
    A Scalable Virtual Circuit Routing Scheme for ATM Networks
    (1998-10-15) Alaettinoglu, Cengiz; Matta, Ibrahim; Shankar, A. Udaya
    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)
  • Thumbnail Image
    Item
    Stepwise Assertional Design of Distance-Vector Routing Algorithms
    (1998-10-15) Alaettinoglu, Cengiz; Shankar, A. Udaya
    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)
  • Thumbnail Image
    Item
    The Viewserver Hierarchy for Inter-Domain Routing:Protocols and Evaluation
    (1998-10-15) Alaettinoglu, Cengiz; Shankar, A. Udaya
    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)