A multiple core mode for protocol independent multicast

Francesc Font Torre de Mer
EPFL, 2004
Thèse EPFL

Résumé

Internet communications have traditionally been based on point-to-point connections. This technique is called unicast and allows one sender and one receiver to communicate. The Internet saw the appearance of multicast protocols in the early 90's. Multicast enables point-to-multipoint and multipoint-to-multipoint connections and is suitable for applications with several receivers. Multicast packets are transmitted from each sender to the receivers through a certain multicast tree. Multicast routing protocols are responsible for building such trees. There are different types of multicast routing protocols and each builds a specific kind of multicast tree. The main advantages of applying multicast in multiple-receiver applications are a more rational use of network resources and the minimization of processing in hosts. There are two types of multicast models: Source-Specific Multicast (SSM) and Any-Source Multicast (ASM). The former is suitable for single-source applications like Internet TV and news distribution. The latter supports multiple-source applications like videoconferencing, Distributed Interactive Simulations (DIS), multi-player gaming and interactive distance learning. The Internet multicast research community assumes that both models must co-exist. Protocol Independent Multicast - Sparse Mode (PIM-SM) is the ASM standard basis for intra-domain multicast routing in Wide-Area Networks (WANs). This protocol builds Shared Trees (STs) rooted at certain routers called Rendezvous Points (RPs). These types of trees bring some drawbacks, the most important being traffic concentration, sub-optimal forwarding of multicast packets and slow convergence when an active RP fails. Two proposals arose to alleviate these drawbacks. The first, Bidir-PIM, constructs Bi-directional Shared Trees (BSTs). However, this variant neglects the problem of having a single point of failure. The second assembles Multiple Core Trees (MCTs) and is based on two protocols, PIM-SM and Multicast Source Discovery Protocol (MSDP), used in combination with anycast. MSDP has been adapted from inter-domain multicast to enable PIM-SM to use several RPs per group. On the other side, anycast allows senders and receivers to send data and control packets to the closest RP. If a RP fails, anycast also provides an automatic backup to the next closest RP. However, this proposal is complex and is not suitable for bursty sources and the next generation Internet Protocol (IPv6). Furthermore, it suffers from high join latencies and poor multicast state scalability with the number of sources. The first purpose of this dissertation is to provide a comparison on the ìqualityî for the different sorts of multicast trees built in the ASM model by multicast routing protocols suitable to run in WANs. This study concludes that MCTs give the best performance in terms of traffic concentration and link cost of multicast trees in sparse groups and end-to-end delay. Furthermore,it is the only type of tree that does not suffer from a single point of failure, called core or RP. The main purpose of this dissertation is the design of an extension to PIM-SM that allows the building of MCTs without MSDP. The extension to the register mechanism in PIM-SM allows the construction of channels encompassing the Access Routers (ARs) and any number RPs. These channels enable sources to directly reach all the RPs, thus avoiding the exchange of data packets between RPs, which generates additional processing in the RPs and the suboptimal routing of multicast packets coming from new sources. Furthermore, these channels may improve the multicast routing state scalability with the number of sources. This approach, called Protocol Independent Multicast - Multiple Core Mode (PIM-MCM), enables PIM having the advantages of anycast RP without using MSDP. In addition, it conforms to the PIM-SM design philosophy and alleviates all the drawbacks of MSDP while minimizing the added complexity.

Official source

https://infoscience.epfl.ch/record/33498?ln=fr

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

Francesc Font Torre de Mer
EPFL, 2004
Thèse EPFL

Résumé

Official source

https://infoscience.epfl.ch/record/33498?ln=fr

À propos de ce résultat

Concepts associés (10)

Concepts associés

Chargement

Publications associées (14)

Publications associées

Chargement

Scalable routing protocols with applications to mobility

Ljubica Blazevic

In this thesis we study two routing problems related to mobility. The first problem concerns scalable multicast routing when there is a large number of multicast groups with a small number of receivers. Existing dense and sparse mode routing protocols have the following problems when the number of groups is large, but the groups are small: (1) high overhead in control traffic (dense mode), (2) poor utilization of backbone links and (3) complexity of management of single core routers (sparse mode). Our solution to this problem is the Distributed Core Multicast (DCM) routing protocol. DCM is an extension of the core-based tree approach and its architecture is based on several core routers per multicast groups. We explain the objectives achieved with DCM: (1) avoiding state information in backbone routers, (2) avoiding triangular routing across expensive backbone links, (3) scaling well with the number of multicast groups. DCM can be applied to support host micromobility in a large single Internet domain network, where every mobile host is assigned a multicast address in a domain it visits. The advantages of the multicasting-based approach for supporting host mobility are low latency and minimal disruption during handover. The second problem studied in this thesis concerns scalable routing in a large scale mobile ad hoc network. Ad hoc networks have gained increasing popularity in recent years because of their ease of deployment. No wired base station or infrastructure is needed, and mobile nodes communicate with each other using multi-hop wireless links. In ad hoc networks, routing protocols are challenged by the establishment of and the maintenance of multihop routes in the face of mobility, bandwidth limitation and power constraints. Routing protocols that rely on state concerning all links on the network, or all links on a route between a source and a destination result in poor scaling properties in larger mobile ad hoc networks. Position-based routing protocols are better suited for large mobile ad hoc networks. These protocols use the positions of nearby nodes and of packet's destination to make the packet forwarding decisions. We present a scalable routing protocol for a large mobile ad hoc network that is called terminode network. We call the nodes terminodes because they act as network nodes and terminals at the same time. Our routing scheme is a combination of two protocols called Terminode Local Routing (TLR) and Terminode Remote Routing (TRR). TRR is activated when the destination is remote and it uses the location of the destination obtained either via location management or by location tracking. TLR acts when the packet gets close to the destination and it uses routing tables that are built by nodes for close terminodes. The use of TRR results in a scalable solution that reduces dependence on the intermediate systems, while TLR allows to increase the probability of reaching the destination, even when it has moved considerably from the location that was known at the source. We use simulations to demonstrate terminode routing's scalability in different sized mobile ad hoc networks.

EPFL2002

Chargement

Modeling and performance analysis of IP access interface in optical transmission networks with packet switching

The article analyzes the influence of the Internet Protocol (IP) access interface on the packet loss probability and delay times in the optical packet switched network. The network and node model have been proposed, and the structure of the IP access interface, including assembler and holder, have been included in the analysis. It has been shown that the increase of the maximum optical packet sizes, as well as use of the holding feature as contention resolution mechanism, decrease the packet loss probability, but introduce delays at the optical network access points. Modeling and analysis were based on the discrete event simulation assuming self-similar traffic sources. IP packet lengths were modeled using empirical data.

2006

Chargement

State-machine replication (SMR) is a software technique for tolerating failures and for providing high availability in large-scale systems, through the use of commodity hardware. A replicated state-machine comprises a number of replicas, each of which runs an agreement protocol, with the goal of ensuring a consistent state across all of the replicas. In hostile environments, such as the Internet, Byzantine fault tolerant state-machine replication (BFT) is an important technique for providing robust services. During the past decade, we have seen an emergence of various BFT protocols. In order to be adopted, besides providing correctness, a BFT must provide good performance as well. Consequently, all of the new protocols focus on improving performance under various conditions. However, a closer look at the performance of state-of-the-art BFT protocols reveals that even in best-case execution scenarios, they still remain far behind their theoretical maximum. Based on exhaustive evaluation and monitoring of existing BFT protocols, we highlight a few impediments to their scalability. These obstructions include the use of IP multicast, the presence of bottlenecks due to asymmetric replica processing, and an unbalanced network bandwidth utilization. The goal of this thesis is to evaluate the actual impact of these scalability impediments, and to offer a solution for a high-throughput BFT protocol in the case in which the network itself is the bottleneck. To that end, we have developed Ring, a new BFT protocol which circumvents the aforementioned impediments. As its name suggests, Ring uses the ring communication topology, in the fault-free case. In the ring topology, each replica only performs point-to-point communications with two other replicas, namely its neighbors on the ring. Moreover, all of the replicas equally accept requests from clients and perform symmetric processing. Our performance evaluation shows that, with the network as the bottleneck, Ring outperforms all other, state-of-the-art BFT protocols. Ring achieves 118 Mbps on the Fast Ethernet – a 24% improvement in throughput over previous protocols. Finally, we conducted an extensive practical and analytic evaluation of Ring. In order to analyse benefits (and drawbacks) of Ring (and other protocols) under different settings, without resorting to costly experimentation, we developed an analytical performance model. Our performance model is based on queueing theory, and relies only on a handful of protocolagnostic measurements of the environment.

EPFL2012

Chargement

EPFL2012

Scalable routing protocols with applications to mobility

Ljubica Blazevic

EPFL2002