Search

The existing protocols for the Internet connectivity of Mobile Ad Hoc Networks suffer from a high overhead since they often rely on flooding in executing mobility management and/or route discovery. In this paper, we propose a tree link state routing protocol in which a mobility management protocol builds topology information at the Internet Gateway (IG) as well as manages mobile nodes using tree topology and a routing protocol exploits the topology information, tackling the inherent problem of the excessive control overhead which appears in link state routing protocols. The activities of routing protocol including the delivery of data packet and control message also help the update of the topology information. In this way, mobility management and routing protocol collaborate with each other to increase convergence speed of topology and reduce control overhead. In addition, the progressive path discovery and the message aggregation technique based on the skewed wait time assignment are employed to reduce control overhead of the nodes near the Internet Gateway that process much more data packets and control messages. Simulation results show that the proposed method far outperforms AODV-Hybrid and OLSR+.

Routing is one of the most challenging development issues in Delay-Tolerant Networks (DTNs) because of lack of continuous connection. Existing routing schemes for DTNs provide best effort service, but are unable to optimize QoS and support message priority. In this paper, we present a Look-Ahead Routing and Message Scheduling approach (ALARMS) which exploits more accurate knowledge about various parameters regarding routing to achieve better QoS in the DTN. We assume a variation of the well-known ferry model, in which there are ferry nodes moving along pre-defined routes to exchange messages with the gateway node of each region on the route and also pass to the gateway nodes look-ahead routing information about when it will arrive at each gateway node on the route in the next two rounds and how long it will stay. The gateway nodes use this information to estimate the delivery delay of each message when being delivered by different ferries, and schedule the message to be delivered by the ferry which arrives earliest at the destination. Simulation results show that ALARMS outperforms three existing routing protocols: epidemic routing, Spray-and-Wait, and Spray-and-Focus, in terms of delay time, delivery ratio, and overhead. We also discuss five enhancement strategies on ALARMS and how ALARMS can support message prioritization.

Internet Service Providers (ISPs) often collect routing data to troubleshoot, analyze and predict the behavior of their network. However, data collected from multiple interacting routing protocols is often incomplete and difficult to manually analyze. In this paper we present a systematic approach to combine the pieces of measured routing data to obtain a more complete picture of a network's routing state. Our technique is efficient, has no assumptions about router configuration and is accurate. We present a case-study of a large Tier-2 ISP, finding that for those routers with adequate measurement infrastructure, we consistently find the egress location for 99.9999% of (router,prefix) pairs. Further, for the 85% of routers without measurement infrastructure we predict their decisions. This technique has been successfully applied in a 'what-if' scenario and has future applications in the real-time analysis of routing decisions.

In traditional approaches to energy-efficient routing, a node needs to receive routing messages from all of its neighbors to be able to select the best route. In this work, we propose a technique that enables the best route selection based on exactly one message reception. We call the resulting routing protocol O(1)-reception. In O(1)-reception, each node delays forwarding of routing messages (RREQs) for an interval inversely proportional to its residual energy. This energy-delay mapping technique makes it possible to enhance an existing min-delay routing protocol into an energy-aware routing that maximizes the lifetime of sensor networks. We also identify comparative elements that help us to perform a thorough a posteriori comparison of the mapping functions in terms of the route selection precision. Simulation results show that our mapping functions select routes with very high precision while keeping the propagation delay of routing messages reasonable. In addition, we show that redundant messages filtering significantly extends lifetime of sensor networks compared to classical maximum lifetime approaches in which no filtering is applied.

Zone Routing Protocol (ZRP) provides a flexible solution for discovering and maintaining routes in the MANET. By adopting the idea of Fisheye State Routing in ZRP, a more efficient protocol called Fisheye Zone Routing Protocol (FZRP) was proposed in the paper. FZRP provides the advantage of a larger zone with only a little increase of the maintenance overhead. Two levels of routing zone are defined in FZRP: the basic zone and the extended zone. Different updating frequencies of changes of link connectivity are associated with the basic zone and extended zone. Simulation study has shown that FZRP is more efficient than ZRP in terms of route finding cost with only a little increase of the maintenance overhead.

In this paper, we propose a so-called refinement-based routing protocol that uses dynamic route redirection to provide proactive route selection and maintenance to on-demand routing algorithms so that the benefits of both types of routing algorithms can be combined and their drawbacks minimized. This refinement-based routing protocol includes two major mechanisms. The first is designed to prevent path-breaks by introducing a proper redirector in the vicinity of a potential link-break to bypass the weak link. The second efficiently adds automatic route shortening benefits, which can be done with normal proactive routing algorithms, to on-demand routing algorithms without periodically exchanging routing messages. Using information overheard from neighbors, the mechanism aggressively searches for a redirector that can shorten an on-going route. Experimental results demonstrate that adding the refinement-based routing protocol to AODV significantly reduces the number of broken paths and the end-to-end packet latency when compared with the pure on-demand routing protocol, AODV.

Differentiated services (DiffServ) is the latest model proposed by Internet engineering task force (IETF) to support quality of service (QoS) in the Internet. It has flexibility and scalability advantages over the earlier model, namely, integrated services (IntServ). Currently, the DiffServ model is the preferred architecture widely accepted by Internet providers and the networking research community. The goal of the DiffServ model is to avoid maintaining large amount of state information in core routers, and carry out aggregate resource reservation at edge routers. Therefore, DiffServ calls for a very different routing framework from IntServ. In this paper, we propose two new QoS-based routing algorithms under the single service, multiple options (SiMO) framework for DiffServ architectures. These are kth-shortest QoS routing (kthQoSR) and maximum energy value QoS routing (EVQoSR). We also introduce QoS extensions to OSPF and compare it to our SiMO routing protocols. Our core routing strategy in SiMO, kthQoSR, is executed at the path level and selects one or more routes from a set of computed routes according to defined selection metrics. On the other hand, EVQoSR is a link level, online distributed routing algorithm. Through extensive simulations, we demonstrate that our proposed SiMO routing framework can achieve better route qualities in terms of load balancing, and network throughput.

Nowadays, the commonly used table lookup scheme for IP routing is based on the so-called classless interdomain routing (CIDR). With CIDR, routers must find out the best matching prefix (BMP) for IP packets forwarding, which complicates the IP lookup. Currently, this process is mainly done in software and several schemes have been proposed for hardware implementation. Since the IP lookup performance is a major design issue for the new generation routers, in this article we propose a fast IP address lookup scheme, which significantly reduces the forwarding table to fit into SRAM with very low cost. It can also be implemented in hardware using the pipeline technique. By using our proposed method, the required memory space can be 90-170Kb less than the previous scheme and three memory accesses for a lookup in the worst case. When implemented in hardware pipeline architecture, our mechanism can achieve one routing lookup per memory access.

Networks deploying hierarchical routing are recursively partitioned into sub-networks that do not reveal the full details of their internal structure outside their domains. Instead, an aggregated view of certain parameters that are associated with traversal within such sub-networks between their border nodes is advertised. The ATM PNNI standard and the Internet Nimrod architecture both adopt this approach for routing. This paper studies the effectiveness of ATM hierarchical routing protocols on networks with different hierarchical structures by simulation. Our study shows that in general, the hierarchical source routing performs well compared to the global routing strategy which imposes no hierarchy, while utilizing less storage and communication overhead. For certain networks and topologies, the hierarchical routing performs better than the global routing. Different hierarchies imposed on the same topologies have significantly different performance on the throughput and routing delay. This suggests the necessity of studying the hierarchy design for communication networks using hierarchical routing.

We propose a simple distance-vector protocol for routing in networks having unidirectional links. The protocol can be seen as an adaptation for these networks of the strategy as used in the popular RIP protocol. The protocol comprises two main algorithms, one for collecting ''from'' information, and the other one for generating and propagating ''to'' information. Like the RIP protocol, this one can handle dynamic changes and tolerate node and link failures in the network.

The loop-free path-finding algorithm (LPA) has been shown to maintain loop-free routing tables and to obtain correct routing tables after topological and link-cost changes faster and with less processing and communication overhead than link-state algorithms and prior loop-free routing algorithms based on vectors of distances. The limitation of LPA and prior routing algorithms based on routing trees has been the fact that, because LPA operates by communicating shortest-path routing trees incrementally among neighbor nodes, it forces routers to maintain more 'host routes' than would be needed in a traditional distance vector algorithm. Maintaining such information incurs additional storage overhead and may not be feasible in some cases (e.g. due to subnetting). To remedy this, and to provide a scalable Internet routing solution, we propose a new hierarchical routing algorithm that combines LPA with the area-based hierarchical routing scheme first proposed by McQuillan for distance-vector algorithms. The new algorithm, which we call the hierarchical information path-based routing (HIPR) algorithm, accommodates an arbitrary number of aggregation levels and can be viewed as a distributed version of Dijkstra's algorithm running over a hierarchical graph. HIPR is verified to be loop-free and correct. Simulations are used to show that HIPR is much more efficient than OSPF in terms of speed, communication and processing overhead required to converge to correct routing tables. HIPR constitutes the basis for future Internet routing protocols that are as simple as RIPv2, but with no looping and better performance than protocols based on link-states.

We analyze the security of the BGP routing protocol and identify a number of vulnerabilities in its design and the corresponding threats. We then present modifications to the protocol that minimize or eliminate the most significant threats. The innovation we introduce is the protection of the second-to-last hop information contained in the AS_PATH attributes by digital signatures, and the use of this predecessor information to verify the path of the selected route. With these techniques, we are able to secure complete path information in near constant space, avoiding the recursive protection mechanisms proposed for BGP in the past.

We present a group routing protocol for a network of processes. The task of the protocol is to route data messages to each member of a process group. To this end, a tree of processes is constructed in the network, ensuring that each group member is included in the tree. To build this tree, the group routing protocol relies upon the local unicast routing tables of each process. Thus, group routing is accomplished by composing two protocols: an underlying unicast routing protocol, whose detailed behavior is unknown but its basic properties are given, and a protocol that builds a group tree based upon the unicast routing tables. The group routing protocol is developed in three steps. First, a simple protocol is obtained, and is proven correct. Then, the protocol is refined twice. Each refined protocol improves upon its predecessor by satisfying all of the predecessor's properties plus some additional stronger properties. The final protocol has the property of adapting the group tree to changes in the unicast routing tables without compromising the integrity of the group tree, even in the presence of unicast routing loops.