Browsing by Subject "Routers (Computer networks)"
Now showing 1 - 2 of 2
Results Per Page
Sort Options
Item Network processor design: benchmarks and architectural alternatives(2005) Lee, Byeong Kil; John, Lizy KurianThe last decade saw phenomenal growth in information technology and network communication. The network interfaces also have to keep up with the speed, throughput and capability to support all the workloads. Network processors (NPs) have recently been introduced in the network interfaces to process complex workloads. This dissertation investigates architectural alternatives for network processors. The network processor should be able to process modern network workloads without slowing down line speed. In order to handle variety of emerging applications, good understanding of the target application from the architectural perspectives is essential. While most of the previous research and commercial products for NPs are dedicated to routing and communication related to data-plane applications, control-plane applications where congestion control and QoS issues are dealt with are not well understood. With the demands of emerging network applications, it is imperative to develop and quantitatively characterize the NP control plane workloads to guide architects for designing future NPs. In this dissertation, a new benchmark suite, called NpBench, is proposed for network processors and its architectural workload characteristics are studied. The NpBench suite includes 5 control plane applications and 5 data plane applications. The NpBench suite is implemented using C and is opened to public. Large number of institutions in the world has licensed and several papers and articles cite the NpBench. The NpBench suite fills a major void that exists in the evaluation and benchmarks of NPs. Another major contribution of this dissertation is architectural enhancements for network processing. First the parallelism characteristics of network processing applications were investigated to see the possibility of identifying it statically. Based on the investigation, it is found that the success of VLIW in the multimedia field can be applied to the network processor domain as a processing element for a parallel architectural implementation. As alternative solutions of existing network processor architectures, hardware acceleration techniques are proposed to deal with new emerging workloads. Also, the feasibility of extracting common ISA extensions over variety of network workloads is investigated for accelerating the capability of a processing element within a parallel architecture.Item Routing and broadcasting over sensor networks(2008-08) Subramanian, Sundar, 1981-; Shakkottai, SanjayAdvances in micro-embedded computing systems, coupled with developments in wireless technology have enabled the deployment of large scale wireless and sensor networks for many important applications. These networks are characterized by local geographic connectivity among nodes and by very little computational and storage capabilities at each node. Moreover, data transfer is mainly through packet forwarding by intermediary nodes. Due to the nature of their connectivity, nodes may have extremely limited information about their network, possibly only of their one-hop neighbors. In such a scenario where the nodes may have limited/erroneous network state information, we study the two basic network primitives: (i) point-to-point routing and (ii) broadcasting. First, we study the problem of point-to-point routing in a network of nodes where each node has a corresponding destination to send/receive data. We consider geographic routing (routing based on the position of the nodes), as this routing scheme is scalable and of low complexity and well suited to operate over sensor networks. We study the effect of imperfect routing information on the path lengths of the individual routes. We provide error models for the routing errors and demonstrate routing strategies that achieve order-wise optimal delays even when only a small fraction of the nodes have any (possibly imperfect) geographic information. We characterize the throughput capacity of the network and show that for a class of progressive routing strategies with limited routing data, the throughput capacity is order-wise optimal. While much of the current research focuses on greedy routing in uniform sensor networks, we study routing in imperfect (anisotropic) networks where greedy geographic forwarding fails due to holes (nodes without any neighbors that are closer to the destination). We develop routing strategies in such networks that operate with geographic location at the nodes to achieve order-wise optimal delays while maximizing the network throughput capacity. These algorithms inherit the beneficial properties of geographic routing algorithms such as scalability and low complexity while providing near-optimal throughput and delay in a robust manner. We also study routing strategies in networks where the traffic demand may be non-uniform. Routing schemes such as geographic routing that minimize some metric of routing distance cause local points of congestion as they do not consider the traffic demands across different parts of the network and may concentrate traffic along some paths that lie across regions of higher demand. We design randomized routing schemes based on geographic routing that are shown to be able to support any traffic demand that is achievable (i.e. achievable by any other scheme). Second, we study the issue of broadcasting in networks with limited local information. We analyze broadcast schemes where nodes have little geographic information or state information (memory of transmitted packets). We demonstrate randomized broadcast algorithms that utilize the limited information and perform broadcasting with minimal transmission overheads. Further, we also study branching random walks in R[superscript d], in the context of broadcasting a message over a spatial network to understand the asymptotic distribution of the broadcast. We derive analytic results on the density of these branching processes