2026-04-17T07:48:05Zhttps://recercat.cat/oai/request

oai:recercat.cat:2117/179262026-02-07T02:16:10Zcom_2072_1033col_2072_452950

00925njm 22002777a 4500 dc Pedroso, Pedro author Papadimitriou, Dimitri author Careglio, Davide author 2011 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) Àrees temàtiques de la UPC::Enginyeria de la telecomunicació::Telemàtica i xarxes d'ordinadors Routing (Computer network management) Telecommunication -- Traffic -- Management Heuristic algorithms IEEE Communications Society Measurement Peer to peer computing Routing Topology Unicast Encaminadors (Xarxes d'ordinadors) Telecomunicació -- Tràfic -- Gestió Dynamic compact multicast routing on power-law graphs