Because of the rapid growth of both traffic and links capacity, the time budget to perform IP address lookup on a packet continues to decrease and lookup tables of routers unceasingly grow. Therefore, new lookup algorithms and new hardware platform are required to perform fast IP lookup. This paper presents a new scheme on top of the NetFPGA board which takes advantage of parallel queries made on perfect hash functions. Such functions are built by using a very compact and fast data structure called Blooming Trees, thus allowing the vast majority of memory accesses to involve small and fast on-chip memories only.
Tomographic techniques allow for the reconstruction of network topologies with no need for cooperation from internal routers. Traditional tomographic techniques infer the internal network layout by clustering nodes into tree structures that, in many cases, reveal only a partial graph structure of the network. This paper proposes a novel approach to network topology discovery by means of packet sandwich probes; the underlying theoretical basis relies on the application of Decision Theory to a finite set of possible topological hypotheses. The decision process is however disturbed by the interaction of probes with regular cross traffic, which results in a background noise that afflicts the measurements. To cope with this phenomenon, a model-free noise reduction technique is also used. The algorithms presented in the paper are validated through extensive simulations in several network scenarios. The results show that such a methodology allows to retrieve a complete picture of the network that includes the detection of all the internal nodes along with the values of capacities of the interconnecting links.
The statistical characteristics of the delay over each link of a network path are a worthy information for different purposes: troubleshooting, traffic engineering, adaptive multimedia flow coding, overlay network design, etc.. However, querying each node on the path in order to retrieve this kind of information can be unfeasible or just too resource demanding. For these reasons many algorithms have been devised in order to infer the internal state of a network based on end-to-end measurements: in fact, the inference of the delay distribution and variance is the focus of this paper. The algorithms which have been proposed in the literature rely on active measurements and are based on a single-sender multiple-receivers scheme, thus requiring the cooperation of a possibly wide number of nodes; notwithstanding, they do not guarantee the possibility of characterizing the delay on each hop of an end-to-end path. On the contrary, the techniques that we propose in this paper are intended to infer the delay distribution and variance over each link of a given network path, based on two-points measurements only. We assess the correctness of our algorithms with reference to widely accepted theoretical results and evaluate their performance through a wide series of model-based and ns2 based simulations.
In grid computing the need for collecting information about both distributed computational resources and network topology and performance is constantly growing. Several tools are currently under development to provide such information. They are based either on a centralized or a distributed architecture. Distributed tools are commonly based on IP-level application- oriented network metrology. The measurements are done by means of beacons running in some network nodes (e.g., grid hosts) and collecting the required information. However, the number of utilized beacons might heavily impact the final result, i.e. the discovered topology and the collected performance information. In this study a model is developed to estimate the percentage of discovered links provided that a specific number of beacons is placed in the network. The model is developed for Erdos-Renyi (ER) graph network models but it can be applied also to other networks. Numerical evaluation shows that the model closely approximate the percentage of discovered links obtained through simulation for ER networks. For other theoretical and real networks the model overestimates the percentage of discovered links. However experimental results show that for networks with realistic average nodal degree the overestimate is less than 20%.
Network Processors (NPs) are attracting and powerful platforms for the fast development of high performance network applications. However, despite their greater flexibility and limited cost with respect to specialized hardware design, NP still face developers with significant difficulties. As they target complex and high-performance applications, programmers are often forced to write assembly code in order to better exploit the hardware. In this paper we propose an approach to NP programming which is based on a three-phase development methodology, and we apply it to Intel NPs of the IXP2XXX family. By exploiting a composition of software tools, a high-level definition of the application is turned first into a distributed program, then into an NP prototype, and finally into an efficient NP executable. The methodology we describe takes advantage of the ASSIST technology, which allows for the porting, testing, modeling and profiling of parallel applications on a cluster of standard PCs. We developed a C library that acts as a communication layer, hiding the hardware details of NP programming and allowing for high performance code development. The ultimate goal of this approach is to let programmers write C code, exploiting ASSIST-provided hints to (1) perform functional debugging and performance analysis and (2) to experiment with different parallel structures. The resulting code can be then directly compiled for the NP without modifications, largely reducing the overall coding effort.
IP address lookup is a fundamental task for Internet routers. Because of the rapid growth of both traffic and links capacity, the time budget to process a packet continues to decrease and lookup tables unceasingly grow; therefore, new algorithms are required to improve lookup performance. However, the large density disparity on the prefix range within real lookup tables suggests a hybrid adaptive technique as effective and simple solution. Therefore, this paper presents a novel approach in which various prefix length ranges are represented with distinct data structures and stored in different memories. In this way, the different frequencies of forwarding rules can be taken in account and the memory hierarchy of real platforms can be exploited. This leads to small structures to be put in fast memory for the most dense ranges and larger structures (with a lower number of accesses) in the slower memories for the other ranges. The results remark the low number of off-chip memory accesses of our scheme and a valuable speedup.
'/%3e%3cuse xlink:href='%23a' transform='rotate(23.036 .093 25.536)'/%3e%3cuse xlink:href='%23a' transform='rotate(45.87 1.273 16.18)'/%3e%3cuse xlink:href='%23a' transform='rotate(69.945 .996 12.078)'/%3e%3cuse xlink:href='%23a' transform='rotate(20.66 -19.689 31.932)'/%3e%3c/svg%3e)