Pasar al contenido principal

Resultados relacionados

Resultados totales (Incluyendo duplicados): 8
Encontrada(s) 1 página(s)

UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Dynamic compact multicast routing on power-law graphs

  • Pedroso, Pedro
  • Papadimitriou, Dimitri
  • Careglio, Davide|||0000-0002-7931-8147
Compact routing schemes address the fundamental tradeoff between the memory space required to store the routing table entries and the length of the routing paths that these schemes produce. This paper introduces the first known name-independent, leaf-initiated dynamic compact routing scheme that allows the distribution of traffic from any source to any set of leaf nodes along a multicast routing path that defines a distribution tree. By means of the proposed scheme, a multicast distribution tree dynamically evolves according to the arrival of leaf-initiated join/leave requests. To evaluate the performance we consider the following metrics: the stretch of the produced routing paths, the size and the number of routing table entries, and the communication cost. The results obtained by simulation on synthetic power law graphs (modeling the Internet topology) show that our scheme can successfully handle leaf-initiated dynamic setup of multicast distribution trees. Two reference multicast routing schemes (the Shortest Path Tree and the Steiner Tree algorithm) are used to compare the performance of the proposed scheme. While increasing the communication cost compared to the Shortest Path Tree, the proposed scheme achieves considerable reduction of the routing table size compared to both reference schemes. Moreover, the stretch of the resulting multicast routing paths show limited deterioration compared to the minimum value obtained with Steiner Trees., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Routing at large scale: advances and challenges for complex networks

  • Sahhaf, Sahel
  • Tavernier, Wouter
  • Papadimitriou, Dimitri
  • Careglio, Davide|||0000-0002-7931-8147
  • Kumar, Alok
  • Glacet, Christian
  • Coudert, David
  • Nisse, Nicolas
  • Fàbrega Soler, LLuís
  • Vila, Pere
  • Camelo, Miguel
  • Audenaert, Pieter
  • Colle, Didier
  • Demeester, Piet M.A.
A wide range of social, technological and communication systems can be described as complex networks. Scale-free networks are one of the well known classes of complex networks in which nodes' degrees follow a power-law distribution. The design of scalable, adaptive and resilient routing schemes in such networks is very challenging. In this article we present an overview of required routing functionality, categorize the potential design dimensions of routing protocols among existing routing schemes, and analyze experimental results and analytical studies performed so far to identify the main trends/trade-offs and draw main conclusions. Besides traditional schemes such as hierarchical/shortest-path path-vector routing, the article pays attention to advances in compact routing and geometric routing since they are known to significantly improve scalability in terms of memory space. The identified trade-offs and the outcomes of this overview enable more careful conclusions regarding the (un-)suitability of different routing schemes to large-scale complex networks and provide a guideline for future routing research., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Nonparametric statistical methods to analyze the internet connectivity reliability

  • Papadimitriou, Dimitri
  • Careglio, Davide|||0000-0002-7931-8147
Facing computational complexity when modeling network reliability by means of parametric models and corresponding statistical methods, in the present study, we apply nonparametric statistical methods, such as the Kaplan-Meier survival probability estimator and the mean cumulative function, to characterize the dynamic properties (in particular, the stability properties) of the Internet routing paths and their relationship with the corresponding forwarding path(s). Providing systematic methodology for quantifying these properties aims at enabling reliability assessment of the Internet connectivity (also referred to as reachability in computer networking). The motivation for studying the dynamic properties (in particular, the stability properties) of the Internet routing paths and their relationship to forwarding paths stems from three main reasons. The first translates the fact that transient but frequent changes in the spatio-temporal properties of routing paths may affect the performance and operating conditions of the corresponding forwarding paths; hence, their reliability. The second reason is that frequent instabilities when observed for the same (subset of) path(s) that can be attributed to a spatially localized portion(s) of the Internet may reveal that the underlying physical topology is more prone to failures; hence, showing limited reliability. The third results from the increasing operational need to provide for a longer term estimation of the Internet routing-forwarding system performance and operating conditions using well-proven statistical analysis accounting for recurrence of events and correlation between instability events. [Best paper award], Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

On the experimentation of the novel GCMR multicast routing in a large-scale testbed

  • Careglio, Davide|||0000-0002-7931-8147
  • Papadimitriou, Dimitri
  • Agraz Bujan, Fernando|||0000-0001-8958-0088
  • Sahhaf, Sahel
  • Perelló Muntan, Jordi|||0000-0001-6563-2664
  • Tavernier, Wouter
Originally defined in the 90s, multicast is nowadays (re)gaining interest given the increasing popularity of multimedia streaming/content traffic and the explosion of cloud services. In fact, multicast yields bandwidth savings complementing cached content distribution techniques and its potential benefits have been verified by studies several times since then (see e.g. [1]). By multicast routing, we refer to a distributed algorithm that, given a group identifier, allows any node to route multicast traffic to a group of destination nodes, usually called multicast group. To enable one-to-many traffic distribution, the multicast routing protocol configures the involved routers to build a (logical) delivery tree between the source and the multicast group, commonly referred to as the Multicast Distribution Tree (MDT). Nevertheless, the scaling problems faced in the 90s still remain mostly unaddressed and worst-case projections predict indeed that routing engines could have to process and maintain in the order of 1 million active routes within the next 5 years [2]., This work has been partially funded by the EULER FP7-258307 and DOMINO (TEC2010-18522) projects., Peer Reviewed
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

On the experimentation of the novel GCMR multicast routing in a large-scale testbed

  • Careglio, Davide
  • Papadimitriou, Dimitri
  • Agraz Bujan, Fernando
  • Sahhaf, Sahel
  • Perelló Muntan, Jordi
  • Tavernier, Wouter
Originally defined in the 90s, multicast is nowadays (re)gaining interest given the increasing popularity of multimedia streaming/content traffic and the explosion of cloud services. In fact, multicast yields bandwidth savings complementing cached content distribution techniques and its potential benefits have been verified by studies several times since then (see e.g. [1]). By multicast routing, we refer to a distributed algorithm that, given a group identifier, allows any node to route multicast traffic to a group of destination nodes, usually called multicast group. To enable one-to-many traffic distribution, the multicast routing protocol configures the involved routers to build a (logical) delivery tree between the source and the multicast group, commonly referred to as the Multicast Distribution Tree (MDT). Nevertheless, the scaling problems faced in the 90s still remain mostly unaddressed and worst-case projections predict indeed that routing engines could have to process and maintain in the order of 1 million active routes within the next 5 years [2]., This work has been partially funded by the EULER FP7-258307 and DOMINO (TEC2010-18522) projects., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Routing at large scale: advances and challenges for complex networks

  • Sahhaf, Sahel
  • Tavernier, Wouter
  • Papadimitriou, Dimitri
  • Careglio, Davide
  • Kumar, Alok
  • Glacet, Christian
  • Coudert, David
  • Nisse, Nicolas
  • Fàbrega Soler, LLuís
  • Vila, Pere
  • Camelo, Miguel
  • Audenaert, Pieter
  • Colle, Didier
  • Demeester, Piet M.A.
A wide range of social, technological and communication systems can be described as complex networks. Scale-free networks are one of the well known classes of complex networks in which nodes' degrees follow a power-law distribution. The design of scalable, adaptive and resilient routing schemes in such networks is very challenging. In this article we present an overview of required routing functionality, categorize the potential design dimensions of routing protocols among existing routing schemes, and analyze experimental results and analytical studies performed so far to identify the main trends/trade-offs and draw main conclusions. Besides traditional schemes such as hierarchical/shortest-path path-vector routing, the article pays attention to advances in compact routing and geometric routing since they are known to significantly improve scalability in terms of memory space. The identified trade-offs and the outcomes of this overview enable more careful conclusions regarding the (un-)suitability of different routing schemes to large-scale complex networks and provide a guideline for future routing research., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Nonparametric statistical methods to analyze the internet connectivity reliability

  • Papadimitriou, Dimitri
  • Careglio, Davide
Facing computational complexity when modeling network reliability by means of parametric models and corresponding statistical methods, in the present study, we apply nonparametric statistical methods, such as the Kaplan-Meier survival probability estimator and the mean cumulative function, to characterize the dynamic properties (in particular, the stability properties) of the Internet routing paths and their relationship with the corresponding forwarding path(s). Providing systematic methodology for quantifying these properties aims at enabling reliability assessment of the Internet connectivity (also referred to as reachability in computer networking). The motivation for studying the dynamic properties (in particular, the stability properties) of the Internet routing paths and their relationship to forwarding paths stems from three main reasons. The first translates the fact that transient but frequent changes in the spatio-temporal properties of routing paths may affect the performance and operating conditions of the corresponding forwarding paths; hence, their reliability. The second reason is that frequent instabilities when observed for the same (subset of) path(s) that can be attributed to a spatially localized portion(s) of the Internet may reveal that the underlying physical topology is more prone to failures; hence, showing limited reliability. The third results from the increasing operational need to provide for a longer term estimation of the Internet routing-forwarding system performance and operating conditions using well-proven statistical analysis accounting for recurrence of events and correlation between instability events. [Best paper award], Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Dynamic compact multicast routing on power-law graphs

  • Pedroso, Pedro
  • Papadimitriou, Dimitri
  • Careglio, Davide
Compact routing schemes address the fundamental tradeoff between the memory space required to store the routing table entries and the length of the routing paths that these schemes produce. This paper introduces the first known name-independent, leaf-initiated dynamic compact routing scheme that allows the distribution of traffic from any source to any set of leaf nodes along a multicast routing path that defines a distribution tree. By means of the proposed scheme, a multicast distribution tree dynamically evolves according to the arrival of leaf-initiated join/leave requests. To evaluate the performance we consider the following metrics: the stretch of the produced routing paths, the size and the number of routing table entries, and the communication cost. The results obtained by simulation on synthetic power law graphs (modeling the Internet topology) show that our scheme can successfully handle leaf-initiated dynamic setup of multicast distribution trees. Two reference multicast routing schemes (the Shortest Path Tree and the Steiner Tree algorithm) are used to compare the performance of the proposed scheme. While increasing the communication cost compared to the Shortest Path Tree, the proposed scheme achieves considerable reduction of the routing table size compared to both reference schemes. Moreover, the stretch of the resulting multicast routing paths show limited deterioration compared to the minimum value obtained with Steiner Trees., Peer Reviewed, Postprint (published version)