1,721,008 research outputs found
A property of structural numbers and cut sets
No full textThe classical theory of structural numbers and its relations with graphs are used in this work to determine a property concerning cut sets in graphs. © 1979 Instituto di Elaborazione della Informazione del CNR
Design and Evaluation of Protocol Stacks for Underwater Communications
No full textThe project revolves around three themes: (i) understanding the physics of acoustic propagation and its impact on the design of communication algorithms and network protocols, (ii) design of network protocols that are theoretically sound and suited to the needs of underwater applications, and (iii) experimental demonstration. The latter activity will benefit from Prof. Basagni collaborations with Woods Hole Oceanograhic Institute and with La Spezia NURC (Nato Underwater Research Center). Such collaborations will allow us to test our ideas in real settings, using equipments whose cost (in the million of Euros) would otherwise be not affordable, having impact on cutting edge ocean engineering
XOR-based schemes for fast parallel IP lookups
No full textAn IP router must forward packets at gigabit speed in order to guarantee a good quality of service. Two important factors make this task a challenging problem: (i) for each packet, the longest matching prefix in the forwarding table must be quickly computed; (ii) the routing tables contain several thousands of entries and their size grows significantly every year. Because of this, parallel routers have been developed which use several processors to forward packets. In this work we present a novel algorithmic technique which, for the first time, exploits the parallelism of the router also to reduce the size of the routing table. Our method is scalable and requires only minimal additional hardware. Indeed, we prove that any IP routing table T can be split into two subtables T-1 and T-2 such that: ( a) | T-1| can be any positive integer k < | T | and | T-2| <= | T| - k + 1; ( b) the two routing tables can be used separately by two processors so that the IP lookup on T is obtained by simply XOR-ing the IP lookup on the two tables. Our method is independent of the data structure used to implement the lookup search and it allows for a better use of the processors L2 cache. For real routers routing tables, we also show how to achieve simultaneously: ( a) | T-1| is roughly 7% of the original table T; ( b) the lookup on table T-2 does not require the best matching prefix computation
- …
