The provision of performance-aware video conferencing services today relies on approaches that focus on data compression and client-side bitrate adaptation techniques to optimize transmission. However, these methods fail to quickly respond to fluctuations in network conditions, thereby compromising the quality of service for transmissions. For this reason, this article aims to propose a novel traffic scheduling-based video transmission optimization solution from the perspective of the network service provider. We first investigate the resource requirements of video conferences and present the experiential performance of video conferences under different network conditions and network competition. Based on these results, we design a service-customized routing mechanism called VCApather that minimizes network contention. We then provide implementation solutions for the control plane and the data plane of VCApather . We evaluate VCApather using a fully meshed topology with five nodes and real-world video conference traffic. The results show that VCApather is capable of achieving high link utilization and balance, while also meeting predefined user metrics. Compared to other schemes, VCApather could satisfy 69.8% more QoE requirements and yielded an average bitrate improvement of 1.74 \(\times\) .

The Acyclic Source-Tree Routing Algorithm (ASTRAL) is introduced to provide loop-free multipath routing in computer networks. With ASTRAL, routers share link-state information only about those links used in their paths to destinations rather than complete topology data, and without requiring periodic messaging. ASTRAL attains loop freedom by making routers coordinate with their immediate neighbors so that they change their next hops to destinations only after routers verify that the data in their topology databases are consistent with the topology data stored at their neighbors. ASTRAL is proven to guarantee loop-free routes at every instant and to converge to shortest paths within a finite time. ASTRAL is shown to be at least as efficient as the ideal link-state algorithm, more efficient than existing link-state routing protocols like OSPF and IS-IS, and more efficient than DUAL, which is the basis of EIGRP.

An efficient approach to distance-based loop-free routing is introduced called THOR (Transitive Hop-Ordered Routing) that, in contrast to all prior distributed routing algorithms and routing protocols, works correctly in the presence of negative link weights. THOR is shown to provide loop-free routing and to converge to shortest paths within a finite time. THOR is compared with OSPF using the ns-3 simulator for the case of minimum-hop routing, and the simulation results show that the approach used in THOR leads to faster convergence and less signalling overhead.

To avoid forwarding loops and the transmission of unwanted replicas of multicast data packets, current multicast routing protocols designed for ad-hoc networks require routers to use packet caches listing enough information about multicast data packets that have been forwarded. In addition, existing multicast-routing solutions for ad-hoc networks either require a multicast routing protocol that operates concurrently with a unicast routing protocol, or adding substantial signaling to the baseline unicast routing protocol. We introduce a new approach for multicasting embedded in unicast routing that eliminates the need to use packet caches for multicasting along shared multicast trees by means of label switching, and incurs minimum additional signaling overhead to attain multicast routing.

Loop-free routing approaches based on distance information combine a Local Ordering Condition (LOC) with a distributed reordering computation (DRC). The LOC allows routers to determine whether they can independently change next hops to destinations without creating a routing loop, and the DRC permits routers re-establish their ordering relative to a destination when the LOC is not satisfied. A new type of DRC called Spreading Computations is shown to be inherently more efficient than DRCs used in existing loop-free routing protocols. A new routing algorithm based on spreading computations is presented and compared with OSPF, DSDV, and RIPv2 using the ns-3 simulator. The results show that using spreading computations results in faster convergence speeds after link or router recoveries or failures.

We propose a network service as a solution for video conference applications by constructing network layer routing strategies. Our approach takes into account the characteristics of conferencing flows, addresses various self-customized metrics, and proactively ensures a positive user experience by preventing contention. The performance of VCApather is evaluated using a fully-meshed topology with five nodes and real-world video conference traffic. The results show that VCApather is capable of achieving high link utilization and balance, while also meeting predefined user metrics. Compared to other schemes, VCApather was found to satisfy 69.8% more QoE requirement and to yield an average bitrate improvement of 1.74×.

The availability of vast computing resources today allows us to reimagine how wireless networks and the Internet at large could operate if far more machine intelligence were used inside the networks themselves, rather than just at the servers and clients using them, and to develop new network architectures and protocols for intelligent digital infrastructures. This paper describes some results of how communication protocols can be reimagined taking into account much larger amounts of working memory capacity and machine intelligence, and outline a research agenda for the development of protocols for intelligent digital infrastructures.

RIPPLE-WiN (Routing Information Protocol with Probing for Looplessness and Efficiency in Wireless Networks) is introduced. RIPPLE-WiN replaces the sequence numbers that are used in popular routing protocols for wireless networks like OLSR, AODV and DSDV to validate updates or support loop freedom with hop-count reference distances. Such reference distances allow routers to eliminate routing-table loops with minimum signaling overhead. Simulation experiments based on the ns-3 simulator are used to illustrate that RIPPLE-WiN is much more effective that OLSR, DSDV and AODV. The simulation results show that RIPPLE-WiN attains better packet delivery rates and delays than the other routing protocols in the presence of failures and mobility while incurring less signaling overhead.

ALOHA with priority acknowledgments (ACK) is transformed into a collision-free channel access method by means of a neighborhood-understood index (NUI). Each node maintains the NUI, which allows nodes to remember all nodes that requested to share the channel and the order in which they should be allowed to transmit. The resulting protocol, ALOHA-NUI, adds signaling packets and NUI information in data packets to maintain the NUI, rather than just remembering that a data packet was sent successfully as in ALOHA. This results in ALOHA-NUI, which is compared with TDMA assuming a fixed transmission schedule, ALOHA with priority ACK’s, and CSMA with priority ACK’s analytically and by simulation. ALOHA-NUI is shown to attain the high throughput of collision-free transmission scheduling methods that usually require clock synchronization while maintaining most of the simplicity of ALOHA with priority ACK’s. ALOHA-NUI is also shown to be fair and to reach stable transmission schedules very quickly.

We introduce the concept of a routing etiquette as the set consisting of the information maintained by routers, local operations that can be carried out on such information, and the information that routers share with one another to reach stable routes using local private policies for path selection. OPERA is presented as one such etiquette. Sufficient conditions for stable and loop-free routing based on OPERA are proven. Based on these results, BGP is proven to be inherently unstable and prone to looping, and the policy mechanisms of BGP are modified slightly to attain OPERA-based BGP (OBGP). OBGP is the first loop-free inter-domain multi-path routing solution based on BGP. OBGP is proven to be stable and loop-free. Well-known examples of systems in which BGP does not converge are used to show the benefits of OBGP.

The Dominant-Distance Routing Information Protocol (DRIP) is introduced for quality-of-service (QoS) routing based on multiple criteria and is proven to be loop-free at every instant and capable of converging to optimal routes if they exist. DRIP is based on the exchange of updates and queries stating reference routing-metric values for destinations. Simulation experiments based on ns3 are used to compare DRIP against the Non-Restarting Vectoring Protocol recently proposed by Sobrinho and Ferreira, as well as OSPF and RIPv2. The results demonstrate that DRIP provides loop-free routing based on multiple performance and policy criteria as efficiently as routing protocols for shortest-path routing.

We introduce THORP (Totally Hop-Ordered Routing Procedure), a simple distributed algorithm for minimum-hop routing that works in much the same way as traditional distance-vector routing algorithms do. THORP eliminates routing-table loops by having routers choose as their next hops to destinations those neighbor routers that are totally ordered based on their current distances, without requiring their next-hop routers to correspond necessarily to minimum-hop paths. THORP is shown to be loop-free, to converge to minimum-hop distances within a finite time, and to be faster than the Diffusing Update Algorithm (DUAL), which is the only loop-free shortest-path algorithm that has been used successfully in practice and is part of Cisco’s EIGRP.

OPERA is a framework recently introduced that formalizes routing etiquettes based on path information. New rules derived from OPERA to provide total ordering among paths are added to the policy mechanisms used in IBGP and EBGP, which results in OPERA-based BGP (OBGP). OBGP is a complete loop-free inter-domain multi-path routing solution based on IBGP and EBGP. OBGP is proven to be stable and loop-free at every instant. Well-known examples of systems in which IBGP and EBGP do not converge are used to illustrate the benefits of OBGP.

A new approach to loop-free shortest-path routing is introduced that uses distance vouchers that attest to the acyclic nature of paths. Routers search and find new shortest paths to destinations without ever creating routing loops by trusting updates originated by routers that vouch being closer to destinations. The new approach is shown to converge faster than prior loop-free shortest-path routing methods.

The Scheduling with Interference Removal Established Network-Wide (SIREN) protocol is introduced to enable the scheduling of transmissions in a way that multiple access interference (MAI) is eliminated in multi-hop networks. Unlike all prior medium access control (MAC) methods, SIREN combats MAI as a network-wide problem rather than as a problem confined within a single broadcast link. SIREN ensures that the receivers of a primary transmitter assigned a transmission turn have no MAI, and allow one or multiple concurrent secondary transmitters to transmit during the same transmission turn, as long as no MAI is created. SIREN is implemented on top of the IEEE 802.11b physical layer to show that it is a viable approach using commercial off-the-shelf hardware. SIREN is proven to ensure interference-free transmission schedules in mesh networks, and simulation experiments in ns-3 are used to illustrate the advantages of SIREN over IEEE 802.11b in terms of goodput, fairness and delays.

Reinforcement learning (RL) has been proposed as a technique that allows nodes to learn to coordinate their transmissions in order to attain much higher channel utilization. Several RL-based approaches have been proposed to improve the performance of slotted ALOHA; however, all these schemes have assumed that immediate feedback is available at the transmitters regarding the outcome of their transmissions. This paper introduces ALOHA-dQT, which is the first channel-access protocol based on the use of RL in the context of slotted ALOHA that takes into account the use of explicit acknowledgments from receivers to senders. As such, ALOHA-dQT is the first RL-based approach for channel access that is suitable for wireless networks that do not rely on centralized repeaters or base stations. ALOHA-dQT achieves high utilization by having nodes broadcast short summaries of the channel history as known to them along with their packets. Simulation results show that ALOHA-dQT leads to network utilization above 75%, with fair bandwidth allocation among nodes.

360-degree video streaming, which is becoming more and more popular as the fast development of VR/AR applications nowadays due to the immersive viewing experience it can offer, poses enormous challenges to the current network infrastructure in terms of high bandwidth and low latency requirements. To address this problem and to ensure the QoE (quality of experience) of end-users, this paper presents CUBIST, a method and system for high-quality 360-degree video streaming in networks with cache nodes at the edge. To the best of our knowledge, it is the first tile-based edge caching solution that incorporates proactive tile prefetching and hierarchical cache organization into reactive caching to maximize the caching benefit while reducing the cost of 360-degree video streaming. Experimental results show that CUBIST can achieve a cache hit ratio of 87 % and improve the effective video bitrate by 12.9 % with most rate transitions being small when compared with the latest FoV-aware edge caching scheme.

Key-Activation Multiple Access (KAMA) is introduced. KAMA organizes the channel into a sequence of equal time slots, uses a distributed election algorithm to determine which of the known nodes have the priority to transmit during each time slot, and uses transmission keys to eliminate the need for special signaling packets or the use of special time slots dedicated for signaling packets. Simulation results in multi-hop networks shown that KAMA is more efficient than TDMA, CSMA, and CSMA/CA.

The Internet Transport Protocol (ITP) is introduced to support reliable end-to-end transport services in the IP Internet without the need for end-to-end connections, changes to the Internet routing infrastructure, or modifications to name-resolution services. Results from simulation experiments show that ITP outperforms the Transmission Control Protocol (TCP) and the Named Data Networking (NDN) architecture, which requires replacing the Internet Protocol (IP). In addition, ITP allows transparent content caching while enforcing privacy.

A new transport protocol is introduced to increase the responsiveness of the network to congestion. The new transport protocol, QUCO, reacts to congestion by selectively dropping off parts of a payload packet (combined with mitigation mechanisms to handle the loss of part of the payload). This packet trimming scheme greatly reduces the variations in the number of the packets going through the network. This allows to set tighter targets on the number of packets in flight and on the depth of the switch buffers. QUCO has less delay and much less delay variations than TCP. The resulting reduction in jitter is extremely useful, especially for media distribution.

The Internet Transport Protocol (ITP) is introduced as an alternative to the Transmission Control Protocol (TCP) for reliable end-to-end transport services in the IP Internet. The design of ITP is based on Walden's early work on host-host protocols, and the use of receiver-driven Interests and manifests advocated in several information-centric networking architectures. The performance of ITP is compared against the performance of TCP using off-the-shelf implementations in the ns3 simulator. The results show that ITP is inherently better than TCP and that end-to-end connections are not needed to provide efficient and reliable data exchange in the IP Internet.

ALOHA with Queue Sharing (ALOHA-QS) maintains most of the simplicity of ALOHA with priority acknowledgments (ACK) and attains the high throughput of transmission scheduling methods that require clock synchronization. Channel access with ALOHA-QS consists of a sequence of queue cycles, with each cycle having one or multiple collision-free transmissions by nodes that have joined the transmission queue and a single request turn to join the queue. The signaling of ALOHA-QS entails adding to packet headers the size of the shared queue, the position of the sending node in the queue, a bit indicating the end of transmissions by the transmitting node, and a bit stating whether or not a new node joined the queue successfully. The throughput of ALOHA-QS is compared with the throughput of TDMA with a fixed transmission schedule, ALOHA with priority ACK's, and CSMA with priority ACK's analytically and by simulation.

A new adaptive transmission protocol is introduced to improve the performance of slotted ALOHA. Nodes use known periodic schedules as base policies with which they collaboratively learn how to transmit periodically in different time slots so that packet collisions are minimized. The Adaptive Policy Tree (APT) algorithm is introduced for this purpose, which results in APT-ALOHA. APT-ALOHA does not require the presence of a central repeater and uses explicit acknowledgements to confirm the reception of packets. It is shown that nodes using APT-ALOHA quickly converge to transmission schedules that are virtually collision-free, and that the throughput of APT-ALOHA resembles that of TDMA, where slots are pre-allocated to nodes. In particular, APT-ALOHA attains a successful utilization of time slots- over 70% on saturation mode.

Queue-Sharing Multiple Access (QSMA) is introduced and analyzed. The new channel-access method consists of establishing and maintaining a distributed transmission queue among nodes sharing a common channel and results in a sequence of queue cycles, with each cycle having one or multiple queue turns with collision-free transmissions from nodes that have joined the transmission queue, followed by a joining period for the current cycle. Nodes can take advantage of carrier sensing to improve the efficiency with which nodes join and use the shared transmission queue. The throughput of ALOHA with priority ACK's, CSMA with priority ACK's, CSMA/CD with priority ACK's, TDMA with a fixed schedule, and QSMA with and without carrier sensing is compared analytically and by simulation in ns-3. The results show that QSMA is more efficient than TDMA with the simplicity of CSMA or ALOHA.

Slotted ALOHA is known to have poor channel utilization (a maximum of 37% when average offered load is one packet per time slot). Reinforcement learning has recently been proposed as a technique that allows nodes to learn to coordinate their transmissions in order to attain much higher network utilization. All reinforcement learning schemes proposed to date assume immediate feedback on the outcome of a packet transmission. We introduce ALOHA-dQT, a reinforcement-learning protocol that achieves high utilization by having nodes broadcast short summaries of the channel history as known to them along with their packets. Our simulation results show that ALOHA-dQT leads to network utilization above 75%, with fair bandwidth allocation among nodes. ALOHA-dQT is the first reinforcement-learning approach applied to slotted ALOHA suitable for ad-hoc networks without centralized repeaters.

Using local caches is becoming a necessity to alleviate bandwidth pressure on cellular links, and a number of caching approaches advocate caching popular content at nodes with high centrality, which quantifies how well connected nodes are. These approaches have been shown to outperform caching policies unrelated to node connectivity. However, caching content at highly connected nodes places poorly connected nodes with low centrality at a disadvantage: in addition to their poor connectivity, popular content is placed far from them at the more central nodes. We propose reversing the way in which node connectivity is used for the placement of content in caching networks, and introduce a Low-Centrality High-Popularity (LoCHiP) caching algorithm that populates poorly connected nodes with popular content. We conduct a thorough evaluation of LoCHiP against other centrality-based caching policies and traditional caching methods using hit rate, and hop-count to content as performance metrics. The results show that LoCHiP outperforms significantly the other methods.

Deploying new routing protocols is an expensive investment with complications from implementation and debugging on different architectures,platforms, network constraints, and algorithmic interpretations. We introduce an alternative to strict algorithmic programming of protocols by introducing Functional Algebraic aTomic Evaluators (FATE). FATE is an information processing engine that evaluates information, using algebra, and acts upon said results. FATE is designed to be highly configurable and flexible to allow rapid development on any platform, or necessary changes. FATE uses an XML configuration file to determine which path is optimal.Changes to routing constraints can be met by changing the configuration file, as oppose to redesigning, testing, and debugging a new algorithm. The FATE platform is designed not only for rapid development, but for accuracy in duplicate functionality on different platforms, and ease of use.

We introduce Ordered Distance Vector Routing (ODVR), which is the first approach that enables on-demand and proactive loop-free routing on a per-destination basis. ODVR establishes a strict total ordering of nodes with respect to any given destination using the distances to that destination and reference distances that nodes responding to route requests must have in order to be allowed to send responses. Destinations send gratuitous route replies to enact proactive routing. In contrast to all prior routing protocols, ODVR does not require source or destination sequence numbers, sequence numbers for messages, path information, source routing, or requiring a router to wait for replies from all its neighbors before making changes to its routing table. It is shown that loop-free on-demand routing cannot be attained simply by using destination sequence numbers and the type of signaling used in AODV (Ad-hoc On-Demand Distance Vector) if messages can be lost and nodes may lose routing state for any reason. It is also shown that ODVR provides loop-free routes at every instant. Simulation experiments using ns3 show that ODVR is more efficient than AODV and OLSR.

A new family of channel-access schemes called KALOHA (for "Knowledge in ALOHA") is introduced. KALOHA consists of modifying the pure ALOHA protocol by endowing nodes with knowledge regarding the local times when packets and acknowledgments are received, and sharing estimates of channel utilization at the medium access control (MAC) layer. The only physical-layer feedback needed in KALOHA is the reception of correct data packets and their ACKs. A simple Markov-chain model is used to compare the throughput of KALOHA with ALOHA and slotted ALOHA. The analysis takes into account the amount of knowledge that nodes have and the effect of acknowledgments and turnaround latencies. The results demonstrate the benefits derived from using and sharing knowledge of channel utilization at the MAC layer. KALOHA is more stable than ALOHA and attains more than double the throughput of ALOHA, without the need for carrier sensing, requiring time slotting at the physical layer, or using other physical-layer mechanisms.

A simple variation of Carrier Sense Multiple Access (CSMA), CUE-CSMA (for Channel Utilization Estimation), is introduced in which the transmission-persistence probability is a function of the perceived average length of idle periods, which is used as a cue of channel utilization. Nodes need not know or estimate the number of nodes in the network. A simple analytical model is used to derive the throughput of CUE-CSMA and compare it with non-persistent and 1-persistent CSMA without having to assume saturation mode as several prior studies have done. The model considers the effect of acknowledgments (ACK) and receive-to-transmit turnaround times. The results clearly show that using estimates of average idle periods as simple cues of channel utilization can provide the benefits of 1-persistent CSMA at light loads and match or outperform non-persistent CSMA at higher loads.

There has been increasing attention to virtual reality applications in recent years, especially to immersive or 360-degree videos that typically consume much more bandwidth than traditional ones. Though all produced data is transferred, only a small part (denoted as Field of View or viewport) is watched by users due to the nature of immersive videos. Obviously, this causes a large waste of network resources. Hence, it is important to define a viewport-dependent streaming transmission strategy by detecting where the user is gazing and the movement of the user's head. Unfortunately, there are few datasets providing this information. In this paper, we propose a tile-based simulation approach to generate the distribution of the user's behavior and to provide information that can be used to optimize future view-dependent streaming protocols. We first characterize the users' viewport pattern from datasets gathered from real users by decomposing the 360-degree stream into tiles and analyzing the frequency and time-interval distribution for each tile. Then, we devise a hierarchical Markov model that incorporates the beta distribution of each tile time interval to predict tile transition. The results show that the simulation tool characterizes the tile sequences of users accurately, performing close to the empirical results.

Carrier-Sense Multiple Access with Transmission Acquisition (CSMA/TA) and channel-access prioritization is presented. CSMA/TA is intended for wireless local area networks of stations endowed with half-duplex transceivers and single antennas. It leverages the small turnaround times of current half-duplex radios to increase the likelihood of having the last transmission from a group of overlapping transmissions succeed, especially if turnaround times are smaller or slightly larger than propagation delays. In CSMA/TA, a station senses the channel before sending a pilot and waits for a short time after sending its pilot before sensing the channel again. If the channel is sensed idle again, the station transmits its data packet. By using appropriate pilot lengths, CSMA/TA allows traffic prioritization at the channel-access level, which supplements traditional output traffic prioritization at stations. It is shown that non-priority CSMA/TA can surpass the performance of such protocols as CSMA, FAMA-PJ, and CSMA/CD if turnaround times are larger than propagation delays, but not too much larger. In addition, it is shown that CSMA/TA can improve traffic prioritization significantly across different traffic classes, under different traffic load proportions, compared to CSMA under the same conditions.

CSMA/CAP (Carrier-Sense Multiple Access with Collision Avoidance and Pilots) is introduced for ad-hoc networks in which each node has a single half-duplex radio. Using carrier sensing to access the common channel, a node with a data packet to send transmits a request-to-send (RTS) packet. If the RTS is sent without interference, the receiver sends a clear-to-send (CTS) packet followed by a pilot. A sender that receives a CTS for itself sends its data packet after a delay to let the pilot be heard and and then transmits its own pilot to make the total transmission time equal to a maximum data-packet length. The receiver sends its ACK after receiving the data packet and pilot from the sender. It is shown that no channel-access protocol based on the traditional RTS-CTS handshake over a single channel can guarantee collision-free transmissions of variable-length data packets and ACK's, and that CSMA/CAP does ensure that data packets and their ACK's are sent without multiple-access interference. The throughput of CSMA/CAP is compared with the throughput of CSMA in networks with and without hidden terminals, and the results show that the overhead of CSMA/CAP to eliminate collisions is small and that CSMA/CAP performs far better than CSMA when hidden terminals are present.

We present and analyze CSMA/CDS, a simple extension of carrier-sense multiple access (CSMA) that attains collision detection (CD) through the collaboration among nodes endowed with half-duplex radios in wireless local area networks (WLAN). CSMA/CDS uses two mechanisms to provide feedback to nodes attempting to transmit data packets concurrently. Using carrier sensing to access the channel, a node transmits a common pilot before sending its data packet, and a designated passive listener sends a collision pilot if it does not hear the common pilot after detecting carrier. This ensures that no collisions of data packets can occur. The throughput of CSMA/CDS is analyzed and compared with the performance of CSMA with priority ACKs and CSMA with collision detection (CSMA/CD), which assumes full-duplex transceivers. The results show that the throughput of CSMA/CDS is much better than the throughput of CSMA and is comparable to that of CSMA/CD.

A new approach for collision avoidance and collision detection in ad-hoc networks of nodes with half-duplex radios is introduced. Rather than using a single busy tone indicating that a receiver is busy, three types of carrier tones sent by receivers or passive listeners indicate that an intended receiver is busy receiving or acknowledging a data packet, or a passive listener has detected a collision. All carrier tones are sent over a single control channel, and the data channel is used only for data and request-to-send (RTS) packets. The Carrier-Tone Multiple Access with Collision Avoidance and Detection (CTMA/CAD) is described and its performance is compared with the performance of DBTMA in a hidden-terminal scenario. The results of the analysis show that CTMA/CAD is a more efficient channel-access method for networks with hidden terminals.

All channel-access protocols designed to date based on carrier sensing (namely CSMA, CSMA/CD, CSMA/CA) and the standards based on them (e.g., IEEE 802.11 DCF) have used transmission strategies that are independent of the state of the protocol. In particular, most protocols assume a non-persistent transmission strategy in which a node with a packet to send that detects a busy channel simply backs off. We introduce the first state-aware persistence strategy for carrier-sense multiple access (CSMA) protocols. A node with a packet to send that detects a busy channel decides to transmit once the channel is free depending on whether the ongoing busy period is successful and how early its local packet is ready relative to the start of the ongoing busy period. We provide a simple unifying analysis for CSMA operating in a wireless network with non-persistence and state-aware persistence. Our analysis considers the use of acknowledgments (ACK) and takes into account the effect that receive-to-transmit turnaround times have on performance. The results show that state-based persistence can provide better throughput values relative to a non-persistent strategy, and that new persistence strategies are needed that tailor the amount of persistence to the channel traffic load.

Prior solutions for routing to multi-instantiated destinations simply adapt existing routing algorithms designed for single-instance destinations, or rely on flooding techniques. In this paper, a new approach for routing to multi-instantiated destinations is introduced, and the Multiple Instance Destination Routing (MIDR) framework is presented as an example of the approach. MIDR uses only distance information to multi-instantiated destinations, without routers having to establish overlays, know the network topology, use complete paths to destination instances, or know about all the instances of destinations. MIDR can be used in name-based content routing, IP unicast routing, multicasting, and anycasting; even in scenarios where the network topology is highly dynamic such as in the case of MANETs. It is shown that MIDR provides multiple loop-free paths to destination instances. Extensive simulation-based experiments performed in the context of MANETs show that MIDR outperforms traditional approaches based on unicast protocols and that it scales to large networks.

The de facto approach to Web security today is HTTPS. While HTTPS ensures complete security for clients and servers, it also interferes with transparent content-caching at middleboxes. To address this problem and support both security and caching, we propose a new approach to Web security and privacy called GroupSec. The key innovation of GroupSec is that it replaces the traditional session-based security model with a new model based on content group membership. We introduce the GroupSec security model and show how HTTP can be easily adapted to support GroupSec without requiring changes to browsers, servers, or middleboxes. Finally, we present results of a threat analysis and performance experiments which show that GroupSec achieves notable performance benefits at the client and server while remaining as secure as HTTPS.

We introduce a simple solution for the support of host mobility in the Internet called DIME (Dynamic Internet Mobility for End- Systems). DIME is based on dynamic address translation between the transport and network layers of end hosts, combined with a new out-of-band protocol that updates host-address bindings between communicating hosts opportunistically. It does not require modifications to the end-host operating systems, end-user applications, existing communication protocols or hardware, or the domain name system and any host-identifier namespace. A number of experiments based on a Linux daemon implementation of DIME are used to show that DIME is deployable on a wide range of hardware, and that it outperforms existing mobility proposals such as MIPv6 and HIP across a wide range of performance metrics.

A new approach to collision avoidance is described that is based on the use of carrier tones sent over a single control channel. A carrier tone can indicate that the sender is busy transmitting a request-to-send (RTS), the receiver is busy receiving a data packet, or the receiver is sending an acknowledgment (ACK). RTS, data packets, and end of transmission (ET) packets are sent over the primary data channel without using carrier sensing. The throughout of the resulting protocol, which we call Carrier-Tone Multiple Access (CTMA), is compared with the throughput of CSMA with collision avoidance (CSMA/CA) protocol and the dual busy-tone multiple access (DBTMA) protocol. The results of the analysis show that CTMA is a more efficient channel-access scheme than the other two approaches.

Prior work on persistent and non-persistent transmission strategies of CSMA and CSMA/CD indicated that no persistence provides better performance; however, this result applies only to a specific approach to persistence. We introduce time-based persistence in which a node with a packet to send that finds the channel busy persists for a limited amount of time, and provide a simple unifying analysis of the impact of time-based persistence in channel-access protocols that use carrier sensing and operate in ad-hoc wireless networks. We focus on CSMA with priority acknowledgments (ACK) and CSMA with collision detection (CSMA/CD) and ACKs. Our analysis takes into account the effect that receive-to-transmit turnaround times have on performance, and shows that CSMA and CSMA/CD with time-based persistence can attain the same throughput values relative to a non-persistent strategy.

Carrier-Sense Multiple Access with Collision Avoidance and Detection (CSMA/CAD) is introduced and analyzed. The new protocol operates in a single channel and consists of taking advantage of self-interference cancellation to enable collision detection (CD) in the context of collision-avoidance (CA) handshakes in multi-hop wireless networks. It is shown that CSMA/CAD eliminates the collisions of data packets in the presence of hidden terminals. The throughput of CSMA/CAD is analyzed and compared with the throughput of CSMA, CSMA/CA, and dual busy-tone multiple access (DBTMA). The analysis results show that CSMA/CAD provides better performance than the other channel-access schemes aimed at combating hidden terminals, and that the throughput degradation due to hidden terminals in CSMA/CAD is limited compared to CSMA.

The Named Data Networking (NDN) and Content-Centric Networking (CCNx) architectures are the leading approaches for content-centric networking, and both require using Interests (requests that elicit content) and maintaining per-Interest forwarding state in Pending Interest Tables (PIT) to store per- Interest forwarding state. To date, PITs have been assumed to be necessary to enable native support for multicasting in the data plane, such that multicast forwarding trees (MFT) are established by the forwarding and aggregation of Interests using PITs. We present a new approach to content-centric networks based on anonymous datagrams that provides native support for multicasting, but does so without the need to maintain per-Interest forwarding state. Simulation experiments are used to show that the proposed new approach attains the same end-to-end delays for multicasting while requiring orders of magnitude fewer forwarding entries.

The way in which addressing and forwarding are implemented in the Internet constitutes one of its biggest privacy and security challenges. The fact that source addresses in Internet datagrams cannot be trusted makes the IP Internet inherently vulnerable to DoS and DDoS attacks. The Internet forwarding plane is open to attacks to the privacy of datagram sources, because source addresses in Internet datagrams have global scope. The fact an Internet datagrams are forwarded based solely on the destination addresses stated in datagram headers and the next hops stored in the forwarding information bases (FIB) of relaying routers allows Internet datagrams to traverse loops, which wastes resources and leaves the Internet open to further attacks. We introduce PEAR (Provenance Enforcement through Addressing and Routing), a new approach for addressing and forwarding of Internet datagrams that enables anonymous forwarding of Internet datagrams, eliminates many of the existing DDoS attacks on the IP Internet, and prevents Internet datagrams from looping, even in the presence of routing- table loops.

In theory, on-demand routing is very attractive for mobile ad hoc networks (MANET), because it induces signaling only for those destinations for which there is data traffic. However, in practice, the signaling overhead of existing on-demand routing protocols becomes excessive as the rate of topology changes increases due to mobility or other causes. We introduce the first on-demand routing approach that eliminates the main limitation of on-demand routing by aggregating route requests (RREQ) for the same destinations. The approach can be applied to any existing on-demand routing protocol, and we introduce the Ad-hoc Demand-Aggregated Routing with Adaptation (ADARA) as an example of how RREQ aggregation can be used. ADARA is compared to AODV and OLSR using discrete-event simulations, and the results show that aggregating RREQs can make on-demand routing more efficient than existing proactive or on-demand routing protocols.

We show that the mechanisms used in the name data networking (NDN) and the original content centric networking (CCN) architectures may not detect Interest loops, even if the network in which they operate is static and no faults occur. Furthermore, we show that no correct Interest forwarding strategy can be defined that allows Interest aggregation and attempts to detect Interest looping by identifying Interests uniquely. We introduce SIFAH (Strategy for Interest Forwarding and Aggregation with Hop-Counts), the first Interest forwarding strategy shown to be correct under any operational conditions of a content centric network. SIFAH operates by having forwarding information bases (FIBs) store the next hops and number of hops to named content, and by having each Interest state the name of the requested content and the hop count from the router forwarding an Interest to the content. We present the results of simulation experiments using the ndnSIM simulator comparing CCN and NDN with SIFAH. The results of these experiments illustrate the negative impact of undetected Interest looping when Interests are aggregated in CCN and NDN, and the performance advantages of using SIFAH.

Information Centric Multicasting (ICM) is introduced for the support of multicast groups with multiple sources in information centric networks. ICM supports two modalities: source-initiated multicasting and receiver-initiated multicasting. In contrast to all prior multi-source multicast approaches, routers do not have to flood the network from each multicast source, or know about the core or rendezvous point of a given multicast group. A multi-instantiated destination spanning tree (MIDST) is built to interconnect all sources or all receivers of a given multicast group. To disseminate content in a multicast group, receivers can send Interests to the nearest known source, or sources send content to the nearest receiver; either way, content flows over the MIDST to reach all receivers.

On-demand Content Exchange with Adaptive Naming (OCEAN) is introduced as an alternative to content centric networking approaches (NDN and CCN) that require the maintenance of forwarding state of each Interest traversing a router in a Pending Interest Table (PIT). Content routers in OCEAN maintain data answer routing tables (DART) to support the correct forwarding of Interests and responses to such Interests (content or negative acknowledgments) without divulging the identities of consumers who originate Interests. The size of a DART is proportional to the number of routes used by Interests traversing a router, rather than the number of Interests traversing a router. It is shown that undetected Interest loops cannot occur in OCEAN, while the same is not true for CCN and NDN, and that Interests and responses to Interests are forwarded correctly in the absence of failures. OCEAN attains similar latencies than NDN and CCN but incurs orders of magnitude less storage overhead.

The IP Internet architecture is such that applications must bind fixed IP addresses and ports before any other operations can be executed. These early bindings cause bottlenecks, reliability issues, and force applications and protocols to manage complex lower-layer issues. This poses a big challenge to the future of the IP Internet, given the large and growing numbers of nomadic Internet users, the shift in Internet usage from centralized servers to peer-to-peer content sharing, and the popularity of service replication and virtualization. To address these issues, we introduce and evaluate HIDRA (Hidden Identifiers for Demultiplexing and Resolution Architecture), a novel architecture that creates indirection between layers of any network stack. HIDRA enables sockets and protocols to evolve with the IP Internet by hiding all mobility, multihoming, and multiplexing issues from applications, does not induce significant overhead in the protocol stack, preserves backwards compatibility with today's Internet and applications, and does not require or preclude any additional identifiers or protocols to be used in the protocol stack.

We revisit some of the basic premises of the Content Centric networking (CCN) and Named Data Networking (NDN) architectures, which have been proposed as alternatives to the IP Internet architecture in order to support more efficient access to content available in the Internet. We address the large overhead incurred in NDN and CCN by maintaining forwarding state for each Interest traversing a router and for each content-name prefix known to each router. We introduce a new approach designed to provide orders of magnitude reduction in the complexity of the data plane to make content-centric networking much more viable at Internet scale.

The first comparison of the performance of name-based content routing protocols based on distance vectors and link-states is presented. The protocols used for this comparison are the Named-data Link State Routing (NLSR) protocol, which is the main representative of name-based content routing based on link states, and the Distance-based Content Routing (DCR) protocol, which is the first name-based content routing protocol based on distance vectors. In the simulation of NLSR, the signaling of NLSR is simplified to minimize the overhead it incurs sending link state advertisements (LSAs), such that a single transmission is need to send an LSA, rather than multiple transmission as is the case with NLSR. The results of simulations show that the ideal version of NLSR requires fewer control messages to react to changes of name prefixes when the number of replicas is very small, and DCR incurs less signaling overhead to react to topology changes or changes in name prefixes when the number of replicas is large.

In this paper, we present a new protocol for routing in intermittently connected mobile networks that, by periodically exchanging constant-size Counting Bloom filters, assigns to every node in the network probabilities of reaching any destination. The gradients defined by these probabilities are further used to forward data packets towards any node in the network. The proposed protocol is based on two novel operations defined over the Bloom filters, namely, the unary degradation operation that models the loss of topological information as it gets stale or as it is propagated away from the place where it was generated; and the binary addition operation that is used to acquire topological information from other nodes. These two operations are used to implement a probabilistic form of soft state that is defined in terms of the content of the Counting Bloom filters. We present a series of experimental results based on extensive detailed simulations that show that the proposed protocol outperforms the Epidemic routing protocol by delivering more data packets with less delay, while inducing less total overhead in both MANET and VANET scenarios.

We show that the forwarding strategies in the named data networking (NDN) architecture and the original content centric networking (CCN) architecture cannot ensure that Interests return the requested data objects when routing-table loops exist in a stable or dynamic network. We also show that no correct Interest forwarding strategy that allows Interest aggregation can be designed solely on the basis of identifying Interests uniquely in order to detect Interest loops. We introduce SIFAH (Strategy for Interest Forwarding and Aggregation with Hop-Counts). SIFAH prevents or detects Interest loops when Interests are aggregated or forwarded over one or multiple paths. As a result, it is far more efficient than the forwarding strategy in NDN and the original CCN proposal. SIFAH operates by having forwarding information bases (FIB) store the next hops and number of hops to named content prefixes, and by using Interests that state the names of requested content and hop counts that reflect the information in their FIBs.

Abstract A new approach for multiantenna broadcast channels in cellular networks based on multiuser diversity concept is introduced. The technique called opportunistic interference management achieves dirty paper coding capacity asymptotically with minimum feedback required. When there areKantennas at the base station withMmobile users in the cell, the proposed technique only requiresKinteger numbers related to channel state information between mobile users and base station. The encoding and decoding complexity of this scheme is the same as that of point‐to‐point communications, which makes the implementation of this technique easy. An antenna selection scheme is proposed at the base station to reduce the minimum required mobile users significantly at the expense of reasonable increase in feedback. In order to guarantee fairness, a new algorithm is presented that incorporates opportunistic interference management into existing Global System for Mobile communications (GSM) standard. Copyright © 2014 John Wiley & Sons, Ltd.

Tactical and emergency-response networks require efficient communication without a managed infrastructure. Recent work demonstrates that applying information-centric paradigms to the tactical edge can provide performance benefits over traditional address centric approaches. We propose SOCRATIC (SOCial RATe control for Information Centric networks), an approach that unifies replication and network coding to disseminate content by taking advantage of social content and context heuristics. SOCRATIC replicates network encoded blocks according to a popularity index metric that is shared during neighbor discovery. The number of encoded blocks that is relayed to a node depends on its own interest in a data object and its social popularity, i.e., how often and for how long the node meets other nodes. These blocks are subsequently replicated towards the subscriber if a stable path exists. We evaluate an implementation of SOCRATIC through network emulation of a tactical scenario and demonstrate that it can achieve better performance than traditional socially agnostic approaches.

Today's socket API requires an application to bind a socket to a network address before it can use the socket to communicate. Early bindings of names to addresses create significant bottlenecks, reliability problems, and force applications to manage complex lower-layer issues. Many approaches have been introduced to address this problem; however, all prior proposals introduce additional identifiers, modify applications, or require additional protocols in the protocol stack. In contrast, we propose a generalized socket API based on Internet Resource Descriptors (IRDs), which are opaque identifiers used by applications to refer to network resources and are known only within the hosts in which the applications run. IRDs enable sockets to evolve with the Internet by hiding mobility, multihoming, and multiplexing issues from applications, do not induce significant overhead in the protocol stack, preserve backwards compatibility with today's networks and applications, and do not require additional identifiers or protocols to be used in the protocol stack.

Prior solutions for routing to multi-instantiated destinations (e.g., Internet multicasting and any casting, and routing in information centric networks) simply adapt existing routing algorithms designed for single-instance destinations, or rely on flooding techniques. As a result, they are unnecessarily complex and incur excessive overhead. A new approach for routing to multi-instantiated destinations is introduced, and MIDR (Multiple Instance Destination Routing) is presented as an example of the approach. MIDR uses only distance information to multi-instantiated destinations, without routers having to establish overlays, know the network topology, use complete paths to destination instances, or know about all the instances of destinations. MIDR enables routers to maintain multiple loop free routes to the nearest instances of any given destination, as well as to some or all instances of the same destination. It is shown that MIDR provides multiple loop-free paths to destination instances, and that is orders of magnitude more efficient than traditional approaches based on routing to single instance destinations. MIDR can be used in name-based content routing, IP unicast routing, multicasting, and any casting.

We present an analytical framework to investigate the interplay between a communication graph and an overlay of social relationships. We focus on geographical distance as the key element that interrelates the concept of routing in a communication network with the dynamics of interpersonal relations on the corresponding social graph. We identify classes of social relationships that let the ensuing system scale - i.e., accommodate a large number of users given only finite amount of resources. We establish that geographically concentrated communication patterns are indispensable to network scalability. We further examine the impact of such proximity-driven interaction patterns on the throughput scaling of wireless networks, and show that, when social communications are geographically localized, the maximum per-node throughput scales approximately as 1/ log n, which is significantly better than the well-known bound of 1/√(n log n) for the uniform communication model.

Spatial Classification Multiple Access (SCMA) is introduced as an example of using the radio connectivity among nodes for the dynamic establishment of distributed transmission schedules in wireless multi hop wireless networks. The shared channel is organized into transmission frames whose length in number of time slots is defined solely by the need to avoid hidden-terminal interference, rather than some arbitrary number of time slots related to network size. SCMA is shown to attain feasible transmission schedules within a finite time, and is compared with representative examples of traditional approaches to medium access control (MAC) based on contention, transmission scheduling, and reservations. The results of the analysis show that SCMA attains higher packet delivery ratio, lower average end-to-end delays, and better useful throughput than traditional MAC protocols.

We propose a hybrid approach for conference applications for Named-Date Networks (NDN). This hybrid approach combines a participant-driven, distributed server-based approach for conference control and management with a server-less approach for media forwarding. The participant-driven, distributed server-based approach provides robust and efficient conference control and management that is resilient to single point of failure and can scale dynamically with any conference size. The server-less media forwarding eliminates traffic concentration and congestion in the network. We have carried out experiments using XMPP-based conference tools over CCNx and have successfully built the media forwarding for two conference tools (audio and whiteboard) on Android platform. This hybrid approach leverages NDN to support robust and efficient conference applications.

We present Multi-root Automatic Incremental Routing (MAIR), an efficient routing approach for mobile ad hoc networks (MANET). MAIR has a low routing stretch (ratio of selected path to shortest path length) and provides multiple paths to each destination. Every node is assigned multiple prefix labels with respect to multiple roots in the network. The roots are distributed in the network such that the paths calculated from each of the root labels are as disjoint as possible from each other. The labels of a node are stored distributively in hash tables at “anchor nodes” across the network. Data packets are routed using the distributed hash table (DHT) lookup and longest prefix match with neighbor labels. This eliminates the need to maintain large routing tables in the nodes, which substantially reduces the routing state at each node. A region of interest (ROI) is formed around each active source-destination pair using the node labels. The nodes in the ROI maintain the most recent mapping of the node identifier of a destination to its labels. This reduces the route establishment delay for the nodes inside ROI as the need for DHT lookup is reduced.

CSIR (Cellular Scheduling with Interest-driven Routing) is proposed for the effective dissemination of real-time and elastic traffic in wireless ad-hoc networks. CSIR is a novel cross-layer framework consisting of five components: flow-based priority queuing of packets, distributed interest-based routing, distributed transmission scheduling, a neighbor protocol, and bandwidth reservations. Nodes are scheduled for transmission in coordination with the routes established and the end-to-end delay and bandwidth requirements of the flows. Most of the signaling overhead for active flows is confined to the nodes that are required to maintain them. Results from detailed simulations indicate that, compared to a protocol stack consisting of IEEE 802.11e for channel access, AODV and OLSR for unicast routing, and ODMRP for multicast routing, CSIR attains much better performance in terms of packet delivery and end-to-end delay for elastic and real-time unicast and multicast traffic.

We introduce ORTHCA (On-demand Routing with Two Hop Coordinates Awareness) a method for minimizing the dissemination of route requests in mobile ad hoc networks (MANET). The selection of relaying nodes is implemented by first computing the best two-hop relay nodes R2(u) whose Euclidean Distance to four polar points are the shortest among all two-hop neighbors N2(u), and then determining one-hop relay nodes R1(u) connecting with R2(u). This process is iterated by each member of R2(u). We prove that all nodes in a connected MANET are covered in the dissemination of route requests using this procedure, and that |R1(u) + R2(u)| ≤ 16, which constitutes complexity O(1), regardless of the density of the network. ORTHCA is compared with representative routing protocols, namely AODV, OLSR, LAR, and THP. The simulation results show that ORTHCA reduces the routing load and improves packet delivery ratios, outperforming the other four routing protocols.

The Adaptive Publish-subscribe Distance Vector (APDV) protocol is introduced as an example of a new approach to allowing distance-vector routing to scale by integrating it with adaptive publish-subscribe mechanisms. APDV combines establishing routes to well-known controllers using distance-vector signaling with publish-subscribe mechanisms. The latter allow destinations to publish their presence with subsets of controllers, and sources to obtain routes to intended destinations from those same controllers. Controllers are selected dynamically using a fault-tolerant distributed election algorithm to ensure that each non-controller node is covered by at least a given number of controllers within a few hops. Extensive simulation experiments are used to compare APDV with AODV and OLSR, which are representative protocols for on-demand and proactive routing. The results show that APDV achieves significantly better data delivery, attains comparable delays for delivered packets, and incurs orders of magnitude less control overhead than AODV and OLSR, even under heavy data loads.

Opportunistic routing is studied as a representative example of location-aware greedy routing schemes. The routing process between an arbitrary source-destination pair is modeled as a directed random walk between the two ends in the underlying graph. The mean number of transmissions as well as the average multi-hop distance between arbitrary nodes are unified under a conceptual measure called expected length of the opportunistic walk in the induced network graph. We model this quantity as the mean time to absorption in a finite-state Markov chain. An explicit closed-form expression is presented to approximate the results and tight bounds are given. The accuracy of the results predicted by the analytical model is verified through simulation experiments. We also demonstrate an application of the foregoing model in defining proximity-based social models and identifying classes of social networks that are scalable.

Flooding of route requests or link states is a necessity in many routing protocols for mobile ad hoc networks (MANET), and several mechanisms have been devised to make flooding more efficient; however, all flooding approaches to date are such that the number of neighbors each node must use to relay a flooded packet grows as the node density increases. A new method, called ORCA (On-demand Routing with Coordinates Awareness) is introduced for the dissemination of route requests in MANETs. The selection of relaying nodes at each node in ORCA is done by computing the shortest Euclidean Distance from all neighbors of the node to four polar points located in the transmission range of the node. We prove that ORCA guarantees the coverage of all nodes in a connected MANET, and that the number of relays for each node is at most six. ORCA is compared with representative routing protocols, namely AODV, OLSR, LAR, and THP. The simulation results in networks of 200 and 250 nodes show that ORCA incurs the smallest routing load while attaining average delays and packet delivery ratios that are comparable to or better than those obtained with the other four routing protocols.

The capacity of a wireless network is studied when nodes communicate with one another in the context of social groups. All the nodes are assumed to have the same number of independent long-range social contacts, one of which each selects randomly as its destination. The Euclidean distance between a source and its social group members follows a power-law distribution and communication between any two nodes takes place only within the physical transmission range resulting in communication over multi-hop paths. The capacity order of such a composite network is derived as a function of the number of nodes, the social-group concentration, and the size of social groups. Our results demonstrate that when each node has constant number of contacts which does not increase with network size growth, and are geographically concentrated, then the network behaves similar to social networks and communication network does not have any effect on the throughput capacity. On the other hand, when the social contact population grows in time, or social connectivity among nodes is highly distributed, then the communication network is the dominant factor and the composite network behaves similar to wireless networks, i.e., the capacity is the same as Gupta and Kumar results. When neither social connectivity nor communication network is dominant, then the throughput capacity results are between these two extreme cases.

We present Multi-label Automatic Routing (MAR), the first compact routing protocol that attains a low path stretch (ratio of selected path length to the optimal path length) while maintaining a low routing state for mobile networks. MAR is resilient to node movements in the network. In MAR, nodes assign themselves labels based on their location in the network through a distributed algorithm. Distributed Hash Tables (DHTs) for the node to label mappings are established in some anchor nodes. Once the labels are established, the routing is automatic based on the positional labels of the nodes and DHT lookups. This eliminates flooding completely. Unlike traditional routing protocols MAR does not need destinations-based routing tables. Hence, MAR has a small routing state. With the use of multiple labels per node, the average path length is close to the shortest path and there are multiple paths between source and destination nodes. In Qualnet simulations MAR shows a path stretch close to or better than traditional table-driven and on-demand protocols like OLSR and AODV. Simulation results also show shorter end-to-end delays due to the automatic routing. The delivery ratio of MAR is comparable to these traditional protocols but with a significantly lower network overhead.

A cross-layer framework is introduced for the effective dissemination of real-time and elastic traffic in multihop wireless networks called Scheduling and Traffic Management in Ordered Routing Meshes (STORM). Unicast and multicast routes are established in coordination with the scheduling of transmissions and bandwidth reservations in a way that bandwidth and delay guarantees can be enforced on a per-hop and end-to-end basis. The routes established in STORM are shown to be loop-free and real-time packets forwarded along these routes are shown to have bounded end-to-end delays. Results from detailed simulation experiments show that, compared to a protocol stack consisting of 802.11 DCF for channel access, AODV or OLSR for unicast routing, and ODMRP for multicast routing, STORM attains similar or better performance for elastic traffic, and up to two orders of magnitude improvement in end-to-end delays, with twice the amount of data delivery for real-time traffic while inducing considerably less communication overhead.

We proposed an analytical model to study the interplay between medium access control (MAC) and packet forwarding disciplines in multihop wireless networks. The model jointly considers the channel access procedure and the active portions of the topology, which is determined by packet forwarding discipline. The model allows the computation of per-node performance metrics for any given network topology and the combination of specific MAC protocols and packet forwarding methods. As an example of the applicability of our modeling framework, the analytical model is used to study the performance of multihop wireless networks using a contention-based MAC protocol (the IEEE 802.11 distributed coordination function) and a schedule-based MAC protocol (NAMA), together with different packet forwarding schemes in multihop networks. The analytical results derived from the model are validated with discrete-event simulations in Qualnet; the analytical results are shown to be very close to those attained by simulations.

We present an algorithm to assign time slots to nodes in a TDMA network that minimizes the jitter in time slot assignments. By reducing the jitter in time slots around the TDMA frame, we can provide more consistent network access and reduce the overall delay seen by an application with time-varying traffic patterns, such as normal web traffic. Our algorithm can reduce the average delay seen by all nodes in a network by up to 51%, based on our numerical analysis. The algorithm is designed for TDMA MAC layers where a node has the potential to reserve some number of time slots out of a larger selection of available slots, and one wishes to choose the slots that most evenly distribute them around the TDMA ring. The algorithm solves the Minimum Variance Placement problem for the special case of a directed ring. After describing an exact solution using dynamic programming, we present a much faster run time heuristic that closely approximates the exact solution.

Multi-antenna systems can provide greater throughput and range coverage than traditional single antenna systems. A key aspect of exploiting this new physical layer (PHY) is rate adaptation, which consists of finding the best rate for sending data packets. Unlike rate adaptation in single antenna systems, nodes have many choices apart from adapting different modulation types, and these choices include using spatial multiplexing or transmit diversity, types of guard intervals, and channel width. We present an evaluation and implementation of a new rate adaptation scheme for multi-antenna systems applicable to off-the-shelf wireless cards. Our rate adaptation scheme, rate adaptation for multi-antenna systems (RAMAS), is simple and practical, and eliminates the complexity of the rate adaptation approaches proposed for IEEE 802.11n in the recent past. Extensive experimental evaluation is used to show that RAMAS performs consistently better than many current IEEE 802.11n rate adaptation schemes with much less complexity, and that RAMAS is especially efficient in multi-user and interference-laden environments.

Rate adaptation plays a central role in the efficiency of data transmissions in wireless networks. Due to the complex physical-layer effects of wireless links, including interference, attenuation, and multi-path fading, designing a rate adaptation algorithm that performs well in most scenarios is a challenging problem. We present the Multi-rate Adaptation with Interference and Congestion Awareness (MAICA) scheme, which is compatible with existing 802.11 implementations and relies only on acknowledgment packets for its operation. Extensive simulations, analytical model, and real-world experiments are used to show that MAICA consistently performs better than prior rate adaptation schemes used to date, especially in dense and congested wireless networks.

A new routing metric for multi-hop wireless ad hoc networks is presented. The proposed metric is based on the computation of Signal-to-Noise Ratio (SNR) and minimization of wireless network outage probability in a fading environment. This metric improves the Quality-of-Service by reducing dropped packets. Further, by modeling the network with a Trellis diagram and then using Viterbi Algorithm to select the best routing path, we reduce the routing complexity of our approach. Simulation results demonstrate the improvement achieved by implementation of this new metric. Performance of the proposed metric is compared to other commonly used routing metrics such as Minimum Hop Count (MinHop), Expected Transmission Count (ETX) and two other SNR-based metrics in both mobile and stationary networks.

We study capacity of social networks when nodes communicate in a wireless environment. Such hybrid networks that are combination of wireless communication and social networks are defined as composite networks. Each node has at least one local contact in each of four directions of the network area and q(n) independent long-range contacts, one of which is selected as the destination. We study the throughput capacity for such networks containing n nodes assuming the same number of social contacts for all nodes. The nodes communicate using multi-hop communications through relaying the packet to one of their local contacts until the packet reaches the destination. The distance between source and its long-range social contacts follows power law distribution with parameter α. The order capacity is derived and compared for different values of α and q(n).

Previous work has shown that distributed cooperative MIMO systems (e.g., the hierarchical MIMO cooperation scheme) can provide large gains in capacity if the size of the MIMO systems is a function of the total number of nodes in the network (n). However, no results have been reported on the scaling laws of distributed cooperative MIMO systems when the number of transmit and receive antennas are of finite size, which is the case in real networks. This paper uses the extended network model to demonstrate that, if the size of distributed MIMO systems is restricted to a finite size, then there is at most a constant gain compared to point-to-point communications. Opportunistic interference management (OIM) is introduced as an alternative to distributed MIMO, and it is shown that it provides higher order gains than distributed cooperative MIMO systems under the same assumption of having a finite number of transmit and receive antennas. More specifically, OIM achieves a throughput capacity of C1(n) = Θ (D log log 2/θ log n/√n log n) in fading channels when the transmission range T(n) is Ω (√2/θ n), where θ is a constant parameter close to zero. This constitutes an order gain of Θ(log log 2/Θ log n) compared to point-to-point communications and distributed MIMO systems! Given that it is much easier to implement OIM schemes than distributed cooperative MIMO systems, these results indicate that OIM is a far better choice to making wireless ad hoc networks scale than distributed cooperative MIMO systems.

No abstract available.

The Neighborhood Ordering for Medium Access with Determinism (NOMAD) protocol is introduced. NOMAD defines collision-free transmission schedules dynamically and with no need for a predefined number of time slots per transmission frame by coordinating circular permutations of the identifier of nodes in the neighborhoods shared among nodes. NOMAD is shown to attain feasible transmission schedules within a short finite time and to provide channel access intervals of negligible variance. The performance of the NOMAD is compared with the performance of 802.11 DCF and the node activation multiple access (NAMA) protocol, which is representative of distributed transmission scheduling based on probabilistic elections. NOMAD is shown to attain higher throughput than 802.11 and NAMA in static and dynamic ad hoc networks, and to eliminate the large variances in channel access times present in contention-based schemes and prior transmission-scheduling schemes that do not use reservations.

We define composite networks when nodes communicate only with their long-range social contacts and there is no direct link between a node and its long-range contact. Each node has a single long-range contact and all nodes within its transmission range are local contacts for the node. The long-range contact is the destination for each node in the network and since there is no direct link from source to its destination, nodes communicate using multi-hop communications. This is an extension of the famous work by Kleinberg to random wireless ad hoc networks. The throughput capacity of such networks is studied. The routing is based on each node sending the packets to one of its local contacts until the packets reach the destination. The long-range contact distance from a source follows power law distribution with parameter a which is a characteristic of social networks. A tight bound of throughput capacity for different values of a is derived. The results demonstrate that when a increases or equivalently the distance between source and destination decreases, the throughput capacity increases. For α >; 3, throughput capacity of ⊖(1/ log n) is achieved by utilizing simple point-to-point communications where n is the total number of nodes in the network. This is the maximum feasible throughput that can be achieved in point-to-point communications. The result demonstrates the effect of social groups on wireless ad hoc networks. A new parameter called degradation factor is defined which illustrates the asymptotic behavior of networks for large values of n1.

A Framework for Integrated Routing, Scheduling and Traffic Management (FIRST) in Ad Hoc Networks is introduced. Unicast and multicast routes are established in coordination with the scheduling of transmissions and bandwidth reservations in a way that bandwidth and delay guarantees can be enforced on a per-hop and end-to-end basis. Results from detailed simulation experiments show that, compared to a protocol stack consisting of 802.11 DCF for channel access, AODV or OLSR for unicast routing, and ODMRP for multicast routing, FIRST attains similar or better performance for elastic traffic, and up to two orders of magnitude improvement in end-to-end delays, with twice the amount of data delivery for real-time traffic.

We present the Ordered Proactive Enclave-based Routing for Ad-hoc networks (OPERA) protocol for unicast routing in mobile ad hoc networks (MANETs). OPERA uses source and destination labels to define elliptical interest-driven enclaves to reduce control overhead. A topological sort of destination labels is used for loop freedom. The use of label spacing allows effective local repairs. Simulation results comparing OPERA with traditional routing schemes such as AODV and OLSR show that it has a better delivery ratio and smaller delay in realistic load situations. The network load with OPERA is much smaller than with the traditional on-demand and proactive routing schemes.

We consider a network with n nodes distributed uniformly in a unit square. We show that, under the protocol model, when ns= Ω (log(n)1+α) out of the n nodes, each act as source of independent information for a multicast group consisting of m randomly chosen destinations, the per-session capacity in the presence of network coding (NC) has a tight bound of Θ(√n/ns√mlog(n)) when m = O(n/log(n)) and Θ(1/ns) when m = Ω(n/log(n)). In the case of the physical model, we consider ns= n and show that the per-session capacity under the physical model has a tight bound of Θ(1/√mn) when m = O(n/(log(n))3), and Θ(1/n) when m = Ω(n/log(n)). Prior work has shown that these same order bounds are achievable utilizing only traditional store-and-forward methods. Consequently, our work implies that the network coding gain is bounded by a constant for all values of m. For the physical model we have an exception to the above conclusion when m is bounded by O(n/(log(n))3) and Ω(n/log(n)). In this range, the network coding gain is bounded by O((log(n))1/2).

A framework for integrated multicast and unicast routing in mobile ad hoc networks (MANETs) is introduced. It is based on interest-defined mesh enclaves that are connected components of a MANET spanning the sources and receivers of unicast or multicast flows. The Protocol for Routing in Interest-defined Mesh Enclaves (PRIME) is presented to implement the proposed framework for integrated routing in MANETs. PRIME establishes meshes that are activated and deactivated by the presence or absence of interest in individual destination nodes and groups and confines most of the signaling overhead within regions of interest (enclaves) in such meshes. The routes established in PRIME are shown to be free of permanent loops. Experimental results based on extensive simulations show that PRIME attains similar or better data delivery and end-to-end delays than traditional unicast and multicast routing schemes for MANETs (AODV, OLSR, ODMRP). The experiments also show that signaling in PRIME is far more scalable than the one used by traditional multicast and unicast routing protocols such as AODV, OLSR, or ODMRP.

We present capacity and delay scaling laws for random wireless ad hoc networks under all information dissemination modalities (unicast, multicast, broadcast and anycast) when nodes are endowed with multi-packet reception (MPR) capabilities. Information dissemination modalities are modeled with an (n, m, k)-cast formulation, where n, m, and k denote the number of nodes in the network, the number of destinations for each communication group, and the actual number of communication group members that receives the information (i. e., k ≤ m ≤ n), respectively. We show that Θ(R(n)\√m/k), Θ(1/k), and Θ(R2(n)) bits per second constitute a tight bound for the throughput capacity of random wireless ad hoc networks under the protocol model when m = O(R-2(n)), Ω(k) = R-2(n)= O(m), and k = Ω(R-2(n)), respectively. R(n) denotes the receiver range which depends on the decoding complexity of the nodes. For the minimum receiver range of Θ(√(log n/n)) to guarantee network connectivity, a gain of Θ(log n) for (n, m, k)-casting is attained with MPR compared to the capacity attained when receivers can decode at most one transmission at a time in . Furthermore, we derive the capacity-delay tradeoff of (n, m, k)-casting when MPR is used. We show that the use of MPR can lead to both increased network capacity and reduced delays in wireless ad hoc networks.

ABSTRACT A new routing metric for multihop wireless ad hoc networks is presented. The proposed metric is based on the computation of signal‐to‐noise ratio and path minimization of wireless ad hoc network outage probability in a fading environment. This metric improves the quality of service by reducing the number of dropped packets. Further, by modeling the network with a Trellis diagram and then using Viterbi algorithm to select the best routing path, we reduce the routing complexity of our approach. The performance of the proposed metric is compared with other commonly used routing metrics such as minimum hop count, expected transmission count, and two other signal‐to‐noise ratio‐based metrics in both mobile and stationary networks. Simulation results demonstrate the improvement achieved by this new metric. Copyright © 2011 John Wiley & Sons, Ltd.

We present the CROWN (Collaborative ROuting, scheduling and frequency assignment for Wireless ad hoc Networks) scheme. CROWN is a cross-layer optimization approach for spectrum-agile nodes to adjust their spectrum allocation and transmission scheduling according to the underlying traffic demands. Instead of choosing the optimal route based on predetermined transmission scheduling and frequency assignment results, CROWN incorporates the efficiency of the underlying frequency assignment and scheduling information into the routing metric calculation, so that the route with the maximal joint spatial and frequency reuse is selected. Simulation results show that CROWN efficiently exploits the frequency diversity and spatial reuse features of spectrum-agile radios.

A new cross-layer design taking advantage of OFDMA in ad hoc networks is presented. OFDMA technology is exploited at the physical layer to improve data rate through multiuser diversity and to enhance network throughput by enabling multiple concurrent transmissions over orthogonal subchannels, each consisting of a group of tones. A new tone-assignment algorithm is presented that takes advantage of channel fading and is adapted to the limitations of ad hoc networks and operates alongside the signaling of the resulting medium access control (MAC) protocol called Concurrent Communication medium Access or CoCo-MAC. The new MAC addresses the synchronization requirements of OFDMA and the tone assignment algorithm's necessities, and also enables concurrent initiation of data transmissions from multiple nodes to the same receiver or from a single transmitter to multiple receivers. We present simulation results on the throughput advantages of our technique compared to traditional tone assignment algorithms and MAC protocols based on contention-based avoidance of interference.

Networks based on Ethernet bridging scale poorly as bridges flood the entire network repeatedly, and several schemes have been proposed to mitigate this flooding problem, however, none have managed to eliminate flooding completely. We present Automatic Integrated Routing (AIR) as the first routing protocol that eliminates flooding by assigning prefix labels to switches and building a Distributed Hash Table (DHT). The DHT maps host identifiers to the prefix labels of the switches through which they connect to the network. Each switch is assigned a prefix label using neighbor-to-neighbor messages. Prefix labels denote the locations of the switches in the network, and the prefix labels of any two switches automatically determine one or multiple routes between them. The DHT stores the mapping between the name of a host and its network location (prefix label) in a scalable fashion, with any one switch storing only a fraction of all the mappings. In contrast, prior approaches using DHTs to resolve host names incur the communication and storage overhead introduced by an underlying link-state routing protocol. Results using packet-level traces of Internet traffic demonstrate that AIR attains performance gains of orders of magnitude over Ethernet bridging and prior DHT-based schemes.

We study the scaling laws for wireless ad hoc networks in which the distribution of n nodes in the network is homogeneous but the traffic they carry is heterogeneous. More specifically, we consider the case in which a given node is the data-gathering sink for k sources sending different information to it, while the rest of the s = n - k nodes participate in unicast sessions with random destinations chosen uniformly. We present a separation theorem for heterogeneous traffic showing that the optimum order throughput capacity can be attained in a wireless network in which traffic classes are distributed uniformly by endowing each node with multiple radios, each operating in a separate orthogonal channel, and by allocating a radio per node to each traffic class. Based on this theorem, we show how this order capacity can be attained for the unicast and data-gathering traffic classes by extending cooperative communication schemes that have been proposed previously.

A new context-aware routing framework for multicast and unicast routing in mobile ad hoc networks is introduced. This framework, which is called CAROM (Context-Aware Routing over Ordered Meshes), uses regions of interest to identify connected components of the network that span sources and destinations of interest to restrict signaling to occur mostly within these regions. Context information is used to compute routing meshes composed of shortest-paths located inside of regions of interest. Experimental results based on extensive simulations show that CAROM attains similar or better data delivery and end-to-end delays than traditional unicast and multicast routing schemes for MANETs (AODV, OLSR, ODMRP), and that CAROM incurs only a fraction of the signaling overhead of traditional routing schemes.

The ordering of nodes with respect to destinations of interest by means of spatial information (e.g., distances, path constituency, complete or partial topology) has been a fundamental aspect of all routing protocols in wireless networks. This spatial ordering has also included the use of geographical or virtual coordinates denoting the location of nodes. We propose the use of ordering of nodes based on time rather than space, and without the need to establish any clock synchronization among nodes. We demonstrate for the first time that using the relative times when each node receives and transmits packets is sufficient to establish multiple loop-free paths to destinations, and that such time-based ordering renders more efficient loop-free routing than the spatial ordering of nodes. With the use of self-adjusted delays, nodes can manipulate their ordering so that the resulting routing choices are more robust to failures than routing choices based solely on times driven by the physical topology. Furthermore, we show that the problem of resetting sequence numbers, which is a network-wide operation with traditional spatial ordering, is trivial with temporal ordering. We introduce the Time Ordered Routing Protocol (TORP) and compare it against routing protocols based on spatial ordering to demonstrate that temporal ordering can lead to superior performance in multi-hop wireless networks.

A new cross-layer design taking advantage of OFDMA in ad hoc networks is presented. OFDMA technology is exploited at the physical layer to improve data rate through multiuser diversity and to enhance channel throughput by enabling multiple concurrent transmissions over orthogonal subchannels, each consisting of a group of tones or subcarriers. The proposed Subchannel Selection Algorithm (SSA) addresses the distribution of subchannels and the new Tone Assignment Algorithm (TAS) takes advantage of fading and is adapted to the limitations of ad hoc networks. TAS operates alongside the signaling of the resulting medium access control (MAC) protocol called Concurrent Communication medium Access or CoCo-MAC. The new MAC addresses the synchronization requirements of OFDMA and the needs of the tone assignment algorithm, and also enables concurrent initiation of data transmissions from multiple nodes to the same receiver or from a single transmitter to multiple receivers. We present analysis and simulation results on the throughput advantages of our technique compared to previous spectrum allocation and MAC protocols based on the avoidance of multiple access interference.

An analytical model is introduced for the study of the interplay between medium access control (MAC) and packet forwarding disciplines used in multi-hop wireless networks. The model incorporates the likelihood with which nodes access the channel, which is determined by the MAC protocol, and the creation of active portions of the topology, which is given by the packet forwarding discipline. The model allows the computation of per-node performance metrics for any given network topology and the combination of specific MAC protocols and packet forwarding methods. As an example of the applicability of our modeling framework, the analytical model is used to study the performance of multi-hop wireless networks using a contention-based MAC protocol (the IEEE 802.11 distributed coordination function) and a schedule-based MAC protocol (NAMA), together with different packet forwarding schemes in multi-hop networks. The analytical results derived from the model are validated with discrete-event simulations in Qualnet; the analytical results are shown to be very close to those attained by simulations.

We introduce a new multiuser diversity concept with which multiple transmitters can communicate without causing significant interference to each other. The new scheme, called Opportunistic Interference Management (OIM), significantly reduces the feedback required in distributed Multiple-Input Multiple-Output (MIMO) systems, and requires an encoding and decoding complexity that is similar to that of point-to-point communications. We show that our proposed OIM scheme achieves a per-node throughput capacity of Θ (log(T(n))/√nT(n)) in a wireless network of n nodes and communication range of T(n) = Ω(√log n). This represents a gain of Θ (log(T(n))) compared to simple point-to-point communication. As such, OIM represents a practical alternative to attaining capacity gains similar to those attainable in theory with distributed MIMO systems, and opens up a new area of research for the development of medium access control protocols aimed at managing interference.

Abstract Providing secure routing in mobile ad hoc networks (MANETs) is far more difficult than establishing secure routing in wired networks or static wireless networks. Node mobility and the relative scarcity of bandwidth render prior solutions ineffective. Solutions based on securing link or path information do not work well in MANETs because the dynamic nature of links requires extensive use of flooding to establish effective countermeasures. On the other hand, solutions based on hop‐by‐hop exchanges of distance information are easily compromised. Instead of trying to secure the ordering of nodes, we argue that secure routing in MANETs must be based on the end‐to‐end verification of physical‐path characteristics aided by the exploitation of path diversity to increase the probability of finding secure paths. We apply this approach to the design of the Secure Routing through Diversity and Verification (SRDV) protocol, a secure routing protocol that we show to be as efficient as unsecured on‐demand or proactive routing approaches in the absence of attacks. We prove that the countermeasures used in SRDV can defend against a variety of known attacks to routing protocols, including attacks involving collusion, and the fabrication and modification of routing packets. We also show the effectiveness of the end‐to‐end mechanisms via simulations. Copyright © 2009 John Wiley & Sons, Ltd.

We compute the throughput capacity of random dense wireless ad hoc networks for multi-pair unicast traffic in which nodes are endowed with multi-packet reception (MPR) capabilities. We show that ¿ ((R(n))(1-2)/¿/n1/¿) and ¿ (R(n)) bits per second constitute tight bounds for the throughput capacity under the physical and protocol model assumptions, respectively, where n is the total number of nodes in the network, ¿ > 2 is the path-loss parameter in the physical model, and R(n) is the MPR communication range. In so doing, we close the gap between the lower and upper bounds of throughput capacity in the physical model. Compared to the capacity of point-to-point communication reported by Gupta and Kumar, MPR increases the order capacity of random wireless ad hoc networks under both protocol and physical models by at least ¿(log n) and ¿ ((log n)¿-2/2¿), respectively. We address the cost incurred in increasing the throughput capacity of wireless ad hoc networks over what can be attained when sources and destinations communicate over multi-hop paths under the physical model assumption. We define the power efficiency ¿(n) as the bits of information transferred per unit time (second) in the network for each unit power, and compute such power efficiency for different techniques. We show that a lower power efficiency is attained in order to achieve higher throughput capacity.

This paper presents a mathematical framework for the evaluation of the performance of proactive and reactive routing protocols in mobile ad hoc networks (MANETs). This unified framework provides a parametric view of protocol performance, which in turn provides a deeper insight into protocol operations and reveals the compounding and interacting effects of protocol logic and network parameters. The parametric model comes from a combinatorial model, where the routing logic is synthesized along with the characterization of MAC performance. Each wireless node is seen independently as a two-customer queue without priority, where the two types of customers are unicast and broadcast packets. The model captures the essential behavior and scalability limits in network size of both classes of routing protocols, and provides valuable guidance on the performance of reactive or proactive routing protocols under various network configurations and mobility conditions. The analytical results obtained with the proposed model are in close agreement with simulation results obtained from discreteevent Qualnet simulations.

We study the scaling laws for wireless ad hoc network in which the distribution of nodes in the network is homogeneous but the traffic is heterogeneous. More specifically, we consider the case in which a node is the sink to k sources sending different information, while the rest of the nodes are part of unicast communications with a uniform assignment of source-destination pairs. We prove that the capacity of these heterogeneous networks is ¿(n/Tmax), where Tmaxand n denote the maximum traffic for a cell and the number of nodes in the network, respectively. Equivalently, our derivations reveal that, when n - k ¿ constant, the network capacity is equal to ¿(¿(n/(log n))) for k = O(¿(n log n)) and equal to ¿ (n/k) for k = ¿(¿(n log n)). Furthermore, the network capacity is ¿(1) when n - k = constant. These results demonstrate that the capacity of a heterogeneous network is dominated by the maximum congestion in any area of the network.

In this paper, we present a collision-free asynchronous multi-channel access protocol for Ad Hoc wireless networks using a single transceiver. Our protocol, dubbed AMMAC for Asynchronous Multi-channel Medium Access Control, targets low-cost and low-power deployments where nodes are equipped with a single transceiver. Other distinguishing features of AM-MAC include its simplicity and the fact that it does not require temporal synchronization among nodes. This is accomplished through an asynchronous split phase together with an observation phase as well as an unique handshake. Nodes observe the control channel for a period of time before asynchronously switching to the negotiated channel. Protocol correctness and collision-freedom in a multi-channel environment are verified. We also provide an analytical throughput assessment for our multi-channel approach. Simulation results show that AM-MAC improves performance significantly when compared to IEEE 802.11 and exhibits comparable performance to MMAC, one of the well-known multi-channel medium access control protocols, without the need for temporal synchronization.

We introduce a new multiuser diversity scheme for interference management in cellular networks. A base station with K antennas communicates with at most K out of M mobile stations. It is proven that, if K ¿ M, then K independent data streams can be transmitted to K mobile stations with no need for cooperative joint decoding by such stations. This result is based on a new multiuser diversity concept that allows parallel communication in the network without any cooperation among mobile stations. If the network does not have enough mobile stations, then some of the users need to jointly decode their corresponding data streams. The result suggests the existence of a tradeoff between multiuser diversity and cooperation in the downlink of cellular networks. Our interference management approach is based on a new multiuser diversity concept that achieves the capacity of dirty paper coding (DPC) asymptotically. Surprisingly, this gain is achieved without requiring full channel state information (CSI) and only K integers related to CSI are fed back from mobile stations to the base station. An additional advantage of this scheme is the fact that the encoding and decoding of signals for this distributed MIMO system is based on simple point-to-point communications.

We demonstrate that the gain attained by network coding (NC) on the multicast capacity of random wireless ad hoc networks is bounded by a constant factor. We consider a network with n nodes distributed uniformly in a unit square, with each node acting as a source for independent information to be sent to a multicast group consisting of m randomly chosen destinations. We show that, under the protocol model, the per- session capacity in the presence of arbitrary NC has a tight bound of Theta (1/radic(mnlog(n))) when m = O(n/(log(n))) and Theta(1/n) when m = Omega(n/(log(n))). Our result follows from the fact that prior work has shown that the same order bounds are achievable with pure routing based only on traditional store-and-forward methods.

We present the concurrent transmission or reception multiple access (CTRMA) protocol as an example of embracing interference in wireless ad hoc networks, even when each node is endowed with a single half-duplex radio and a single antenna. CTRMA uses OFDMA to enable each node to either send or receive multiple concurrent transmissions over orthogonal subchannels (groupings of subcarriers). With CTRMA, a node transmits multiple transmissions at the same time by negotiating the subchannels over which transmissions take place by using information attained with a channel priority assignment algorithm. CTRMA supports dynamic bandwidth selection and enhances channel reuse. We prove the correctness of CTRMA and use simulation experiments to illustrate the major performance advantages of CTRMA over prior channel access protocols proposed for single-radio single-channel, single-radio multi-channel and multi-radio multi-channel wireless ad hoc networks.

Providing secure routing in MANETs is far more difficult than in wired networks or static wireless networks. Node mobility and the relative scarcity of bandwidth render prior solutions ineffective. Solutions based on securing link or path information do not work well in MANETs because the dynamic nature of links requires extensive use of flooding. On the other hand, solutions based on hop-by-hop exchanges of distance information are easily compromised. Furthermore, path discovery does not necessarily translate into data delivery. We argue that secure routing in MANETs must be based on the end- to-end verification of physical-path characteristics aided by the exploitation of path diversity to find secure paths. We apply this approach to the design of the Secure Routing through Diversity and Verification (SRDV) protocol, a secure routing protocol that we show to be as efficient as unsecure on-demand or proactive routing approaches in the absence of attacks.

We introduce prefix ordering for efficient multicasting (POEM), the first approach to multicast routing in MANETs in which the network-wide dissemination of control information is independent of the number of groups and sources per group. POEM establishes a labeled directed acyclic graph (LDAG) rooted at an elected node in the MANET and assigns a prefix label to each node denoting its network location relative to the root of the LDAG. Routes between any two prefix labels are implicit in the labels themselves. The sources and receivers of a multicast group use a consistent hashing function to map the identifier of the group (e.g., an IP multicast address) onto the group-prefix-label. The node whose prefix label is the closest match to the group-prefix-label serves as the core of the group. As in prior receiver-initiated multicast approaches, receivers join a multicast group by sending join requests towards the group core, and multicast sources simply forward their multicast data packets towards the cores of the groups. We use simulation experiments to compare POEM with ODMRP and MAODV for different mobility scenarios with varying number of nodes, groups and receivers. The results clearly show that POEM is far more efficient than traditional multicast routing approaches, even in relatively small networks.

Most routing protocols designed for MANETs to date employ breadth-first search (BFS), usually in the form of flooding of route requests or updates, to establish and maintain routes between source-destination pairs. This usually incurs significant overhead, which degrades the performance of the network. In this paper we present a new paradigm for routing protocols operating in MANETs, such that flooding is not required and paths from sources to destinations can be established on demand with time complexity comparable to that of flooding but with significantly less overhead. We introduce the concept of ordered walk as a depth-first based search (DFS) that does not rely on geographical or virtual coordinate information and is more efficient than mere random walks. Using the ordered walk search algorithm (OSA), we demonstrate the potential of using DFS as the building block of the signaling of MANET routing protocols. We introduce the OWL protocol (ordered walk with learning) as an example of efficient DFS-based routing in MANETs, and use simulation experiments to compare its performance against that of three well-known MANET routing protocols based on BFS (OLSR, DSR and AODV). The results show that OWL can achieve comparable these protocols while incurring up to ten times less overhead than AODV.

We present AIR (automatic incremental routing), a unified approach for scalable unicast and multicast routing in mobile ad hoc networks (MANET). In AIR, nodes run a distributed routing algorithm to assign prefix labels to themselves. The labels are assigned such that routing to unicast or multicast destinations is automatic, in that a route from any node to a destination is defined by the node's prefix labels, and incremental, in that no relay node needs to know an entire path to any destination. We verify that AIR provides correct unicast and multicast routing, and present simulation results comparing AIR with AODV, OLSR, MAODV and ODMRP in MANETs. The results from these simulation experiments, as well as from tests carried out in a small testbed running AIR in wireless routers, illustrate that AIR offers substantial performance advantages over traditional unicast and multicast routing protocols, even in the case of small networks.

We show that network coding (NC) does not provide any order gain in the multicast capacity of random wireless ad hoc networks. We consider a network with n nodes distributed uniformly in a unit square, with each node acting as a source for independent information to be sent to a multicast group consisting of m randomly chosen destinations. We show that, in the presence of NC, the per-session capacity under the protocol model has a tight bound of Theta (1/(mnlog(n))) when m = O (n/log(n)) Theta (1/n) when m = Omega (n/log/n). Furthermore, we show that the per-session capacity under the physical model has a tight bound of Theta (1/(mn)) when m = O (n/(log(n))3), and Theta (1/n) when m = Omega (n/log(n)). Prior work has shown that these same order bounds are achievable utilizing only traditional store-and- forward methods.

We introduce the prefix routing over set elements (PROSE) protocol for scalable routing in MANETs based on the combined use of prefix labels and distributed hashing. In PROSE, nodes use neighbor-to-neighbor signaling to label themselves with prefix labels that provide implicit routing from any node to any network destination. Nodes implement a distributed hash table to store the mappings between node identifiers (e.g., a MAC or IP address) and their prefix labels. Destinations publish their existence and sources subscribe to their intended destinations. We show that PROSE provides correct routing based on prefix labels and that its signaling overhead grows sub-linearly with the network size. We present simulation and testbed results that illustrate the benefits of PROSE compared to traditional MANET routing protocols.

We establish a tight max-flow min-cut theorem for multi-commodity routing in random geometric graphs. We show that, as the number of nodes in the network n tends to infinity, the maximum concurrent flow (MCF) and the minimum cut-sparsity scale as ¿(n2r3(n)/k), for a random choice of k = ¿(n) source-destination pairs, where n and r(n) are the number of nodes and the communication range in the network respectively. The MCF equals the interference-free capacity of an ad-hoc network. We exploit this fact to develop novel graph theoretic techniques that can be used to deduce tight order bounds on the capacity of ad-hoc networks. We generalize all existing capacity results reported to date by showing that the per-commodity capacity of the network scales as ¿(1/r(n)k) for the single-packet reception model suggested by Gupta and Kumar, and as ¿(nr(n)/k) for the multiple-packet reception model suggested by others. More importantly, we show that, if the nodes in the network are capable of (perfect) multiple-packet transmission (MPT) and reception (MPR), then it is feasible to achieve the optimal scaling of ¿(n2r3(n)/k), despite the presence of interference. In comparison to the Gupta-Kumar model, the realization of MPT and MPR may require the deployment of a large number of antennas at each node or bandwidth expansion. Nevertheless, in stark contrast to the existing literature, our analysis presents the possibility of actually increasing the capacity of ad-hoc networks with n even while the communication range tends to zero!

We introduce a collaboration-driven approach to the sharing of the available bandwidth in wireless ad hoc networks, which we call many-to-many communication, that allows concurrent multi-packet transmissions (MPTs) and multi-packet receptions (MPRs). Many-to-many communication also permits one-time multi-copy relaying of the same packet, which reduces the packet delivery delay compared to single-copy relaying without any penalty in capacity. Our scheme is based on the integration of multi-user detection and position-location information with frequency and code division in mobile ad hoc networks (MANETs). Transmissions are divided in frequency and codes according to node locations, and successive interference cancellation (SIC) is used at receivers to allow them to decode and use all transmissions from strong interfering sources. Consequently, the interference is divided into constructive interference (COI) and destructive interference (DEI). We show that, if each node is allowed to expand its bandwidth, both the link's Shannon capacity and the per source-destination throughput scale like O(nalpha/2) (upper-bound) and Omega[f(n)] (lower-bound), for n nodes in the network, a path loss parameter alpha > 2, and 1les f(n)alpha/2.

We present the first unified modeling framework for the computation of the capacity-delay tradeoff of random wireless ad hoc networks. This framework considers information dissemination by means of unicast routing, multicast routing, broadcasting, or different forms of anycasting. We introduce (n, m, k) -casting as a generalization of all forms of one-toone, one-to-many, and many-to-many information dissemination in wireless networks. In this context, n, m, and k denote the total number of nodes in the network, the number of destinations for each communication group, and the actual number of communication-group members that receive information (k ¿ m), respectively. We describe the capacity-delay tradeoff for (n, m, k) -casting in wireless ad hoc networks in which receivers perform single-packet reception (SPR). Our results are consistent with prior results in wireless networks and extend them to the general (n,m,k) -cast case.

We present statistical models to accurately evaluate the distribution of the lifetime of wireless links in a mobile ad hoc network (MANET) in which nodes move randomly within constrained areas. We show that link lifetime can be computed through a two-state Markov model and further apply the computed statistics to the optimization of segmentation schemes of an information stream. Summarizing all these results, we further provide a comprehensive analysis on throughput, delay, and storage requirements for MANETs with restricted node mobility.

To minimize energy consumption, efficient broadcasting in ad hoc networks requires the selection of small sets of forwarding nodes and the use of small transmission radii. However, the physical-layer characteristics of radio links are such that receivers may not be able to decode packets sent to them, even without multiple access interference. We present an analytical model to show that the transmission radii used for nodes can be used to establish a tradeoff between minimizing energy consumption and ensuring network coverage. We then propose a mechanism called redundant radius, which involves using two transmission radii, to form a buffer zone that guarantees the availability of logical links in the physical network, one for broadcast-tree calculation and the other for actual data transmission. The effectiveness of the proposed scheme in improving network coverage is validated analytically and by simulation.

We study the broadcast throughput capacity of random wireless ad hoc networks when the nodes are endowed with multipacket reception (MPR) capability. We show that, in such networks, a per-node throughput capacity of Theta(R2(n)) bits per second can be achieved as a tight bound (i.e., upper and lower bounds) for broadcast communication, where R(n) is the receiver range that depends on the complexity of the nodes. Compared to ad hoc networks in which receivers decode at most one transmission at a time, the minimum capacity gain of MPR-based networks is Theta(logn). This is attained when the minimum value for R(n) is used, which equals the minimum transmission range needed to guarantee connectivity in the network (r(n) = Theta(radiclogn/n)).

We present a new perspective on the design and analysis of routing protocols for mobile ad-hoc networks (MANETs). Routing metrics, such as distances or link states, result in an ordering of nodes in the network with respect to the origin of the metric. The manner in which the nodes of a network are ordered can give some insight into the performance of the routing protocol. We show how the use of multiple metrics, an approach we call multidimensional routing, renders orderings among nodes that result in routing protocols that are efficient, more robust, and resilient to link failures. We explain why some routing protocols are inherently more effective than others, which can serve as guidelines for future development of routing protocols for MANETs.

We show that the fundamental problems in providing quality-of-service in the existing Internet architecture has been the assumption that a single, "best" path from source to destination is adequate for any communications requirements of the network. We present a new, best-effort architecture for providing quality-of-service in the Internet based on the use of the "best set of paths" to destinations. We show that this set of paths is well defined, can be efficiently computed, and present an approach to efficiently implement this new, best-effort quality- of-service architecture.

The parallel interaction medium access (PIMA) protocol is introduced to orchestrate channel access in a wireless ad hoc network when nodes are endowed with a single half- duplex radio, and can either transmit multiple packets to multiple destinations in parallel or receive multiple packets from multiple transmitters in parallel using OFDMA. Analytical and simulation results indicate that PIMA attains tremendous improvements in channel throughput compared to MAC protocols aimed at attaining concurrency via traditional channel switching techniques proposed in the past for multi-channel networks.

We present the CROWN (collaborative routing, scheduling and frequency assignment for wireless ad hoc networks) scheme. CROWN is a cross-layer optimization approach for spectrum-agile nodes to adjust their spectrum allocation and transmission scheduling according to the underlying traffic demands. Instead of choosing the optimal route based on predetermined transmission scheduling and frequency assignment results, CROWN incorporates the efficiency of the underlying frequency assignment and scheduling information into the routing metric calculation, so that the route with the maximal joint spatial and frequency reuse is selected. Simulation results show that CROWN efficiently exploits the frequency diversity and spatial reuse features of spectrum-agile radios.

We propose ORCHESTRA, a channel access protocol that uses reservations and virtual MIMO to provide high throughput and bounded channel access delays. Channel access process is divided into a contention-based access period and a scheduled access period. To attain high throughput, nodes build the channel schedule using the contention-based access period, and utilize the spatial multiplexing gain of virtual MIMO links in the scheduled access period. To attain bounded channel access delays, nodes reserve time slots through opportunistic reservations. We evaluate the performance of ORCHESTRA through numerical analysis and simulations, and show that it results in much better throughput, delay, and jitter characteristics than simply using MIMO nodes together with scheduled access (i.e., NAMA) or contention-based access (i.e., IEEE 802.11 DCF).

We present a mathematical framework for the performance evaluation of proactive and reactive routing protocols operating in mobile ad hoc networks (MANETs). The model captures the functionality of the routing protocols together with the characterization of the performance of the medium access control protocol (MAC). It reveals the interplay between the protocol functionality and network parameters, and provides new insight on the relative benefits of proactive and on-demand routing in MANETS. The analytical results are corroborated with results obtained using discrete-event simulations.

This paper introduces an integrated framework for multicast and unicast routing in mobile ad hoc networks (MANET) based on interest-defined mesh enclaves. Such meshes are connected components of a MANET that span the sources and receivers of unicast and multicast flows. We present the Protocol for Routing in Interest-defined Mesh Enclaves (PRIME), which establishes meshes that are activated and deactivated by the presence or absence of interest in destinations and groups, and which confines most of the signaling overhead within regions of interest (enclaves) in such meshes. Experimental results based on simulations show that PRIME attains similar or better data delivery and end-to-end delays than traditional unicast and multicast routing schemes for MANETs (AODV, OLSR, ODMRP), and that PRIME incurs only a fraction of the signaling overhead of traditional routing schemes.

We present an approach that takes advantage of multi-packet reception (MPR) to reduce the negative effects of multiple access interference and therefore increase the capacity of an ad hoc network. We analyze the performance upper bound of joint routing and scheduling for ad hoc networks that embrace interference by using MPR. We formulate the optimization problem under a deterministic model and seek to maximize the aggregate network throughput subject to minimum rate requirements. We then propose a polynomial-time heuristic algorithm aimed at approximating the optimal solution to the joint routing and channel access problem under MPR. We show the effectiveness of our heuristic algorithm by comparing its performance with the upper bound.

We present the first unified modeling framework for the computation of the throughput capacity of random wireless ad hoc networks in which information is disseminated by means of unicast routing, multicast routing, broadcasting, or different forms of anycasting. We introduce (n,m, k)-casting as a generalization of all forms of one-to-one, one-to-many and many-to-many information dissemination in wireless networks. In this context, n, m, and k denote the total number of nodes in the network, the number of destinations for each communication group, and the actual number of communication-group members that receive information (i.e., k lesm), respectively. We compute upper and lower bounds for the (n, m, k)- cast throughput capacity in random wireless networks. When m = k = ominus(1), the resulting capacity equals the well-known capacity result for multi-pair unicasting by Gupta and Kumar. We demonstrate that ominus(1/radic(mnlogn)) bits per second constitutes a tight bound for the capacity of multicasting (i.e., m = k < n) when m les ominus (n/(log n)). We show that the multicast capacity of a wireless network equals its capacity for multi-pair unicasting when the number of destinations per multicast source is not a function of n. We also show that the multicast capacity of a random wireless ad hoc network is ominus (1/n), which is the broadcast capacity of the network, when m ges ominus(n/ log n). Furthermore, we show that ominus (radicm/(kradic(n log n))),ominus(1/(k log n)) and ominus(1/n) bits per second constitutes a tight bound for the throughput capacity of multicasting (i.e., k < m < n) when ominus(1) les m les ominus (n/ log n), k les ominus(n / log n) les m les n and ominus (n/ log n) les k les m les n respectively.

This paper presents the first comprehensive capacity-delay tradeoff study for random wireless ad hoc networks under all information dissemination modalities (unicast, multicast, broadcast, anycast) when nodes operate either with multi-packet reception (MPR) or single-packet reception (SPR) capabilities. Our results demonstrate that for unicast, increasing capacity requires additional delay for SPR similar to the results in [1] while MPR incurs no penalty, i.e., we can increase capacity and decrease delay simultaneously for MPR. For multicast, there is no tradeoff for both SPR and MPR. However, similar tradeoff can be observed for broadcast when MPR is used while there is no tradeoff with SPR.

We establish a tight max-flow min-cut theorem for multicommodity routing in random geometric graphs. We show that, as the number of nodes in the network n tends to infinity, the maximum concurrent flow (MCF) and the minimum cut-capacity scale as Theta(n2r3(n)/k) for a random choice of k ges Theta(n) source-destination pairs, where r(n) is the communication range in the network. We exploit the fact, that the MCF in a random geometric graph equals the interference-free capacity of an ad-hoc network under the protocol model, to derive scaling laws for interference-constrained network capacity. We generalize all existing results reported to date by showing that the per-commodity capacity of the network scales as Theta(1/r(n)k) for the single-packet reception model suggested by Gupta and Kumar, and as Theta(nr(n)/k) for the multiple-packet reception model suggested by others. More importantly, we show that, if the nodes in the network are capable of multiple-packet transmission and reception, then it is feasible to achieve the optimal scaling of Theta(n2r3(n)/k), despite the presence of interference. This result provides an improvement of Theta(nr2(n)) over the highest achieved capacity reported to date. In stark contrast to the conventional wisdom that has evolved from the Gupta-Kumar results, our results show that the capacity of ad-hoc networks can actually increase with n while the communication range tends to zero!

We present Hydra, the first multicast routing protocol for MANETs that establishes a multicast routing structure approximating the set of source-rooted shortest-path trees from multicast sources to receivers, without requiring the dissemination of control packets from each source of a multicast group. Hydra accomplishes this by dynamically electing a core for the mesh of a multicast group among the sources of the group, and aggregating multicast routing state in the nodes participating in multicast meshes, so that only control packets from the core are disseminated towards the receivers of a group. We prove that Hydra establishes correct routes from senders to receivers of a multicast group when multicast state information is aggregated. We also present simulations results illustrating that Hydra attains comparable or higher delivery ratios than ODMRP, but with considerably lower end-to-end delays and far less communication overhead. Results are shown for scenarios using 802.11 and TDMA as the MAC layer protocols.

We present elliptic demarcation of information transfer (EDIT) as a scheme to maintain paths between a source and destination more robustly and limit signaling overhead incurred in mobile ad hoc networks (MANET). EDIT establishes regions of interest on demand, based on distances between a relay node and a source-destination pair, and maintains proactive signaling within this region of interest. We prove the correctness of EDIT, which is based on a progressive sequence numbering scheme, and show that the elliptical regions of interest built by EDIT are more efficient than the traditional use of TTLs, which establish circular, undirected boundaries around destinations. Simulation results comparing EDIT against location aided routing (LAR)[1], AODV[2] and OLSR[3] indicate that EDIT enables on-demand routing that is far more efficient than AODV and OLSR, and is comparable to LAR, but without the need for geo-location information.

We address the cost incurred in increasing the transport capacity of wireless ad hoc networks over what can be attained when sources and destinations communicate over multi-hop paths and nodes can transmit or receive at most one packet at a time. We define the energy efficiency ·(n) as the bit-meters of information transferred in the network for each unit energy. We compute the energy efficiency of many different techniques aimed at increasing the capacity of wireless networks and show that, in order to achieve higher transport capacity, a lower energy efficiency must be attained. Using the physical model, we compute the throughput capacity of random wireless ad hoc networks in which nodes are endowed with multi-packet reception (MPR) capabilities. We show that λ(n)= Θ (R(n))(1-2/α) / n1/α) bits per second constitutes a tight upper and lower bound for the throughput of random wireless ad hoc networks, where α>2 is the path loss parameter in the physical model, n is the total number of nodes in the network, and R(n) is the MPR receiver range. In doing so, we close the gap between the lower and upper bounds for the throughput capacity of wireless networks in the physical model. Compared to the original result derived for plain routing by Gupta and Kumar, MPR achieves a capacity gain of at least Θ((log n)α-2/2α) when RR(n)= Θ(√log n/n).

We introduce the multi-channel flow-aware medium access control protocol, or (MFLAMA), an energy-efficient, schedule-based, multi-channel medium-access control (MAC) protocol designed for data gathering applications in wireless sensor networks. MFLAMA improves the channel utilization by establishing collision-free transmission schedules across multiple channels. Energy efficiency is achieved by preventing packet collisions, idle listening, and transmissions to a node that is not ready to receive packets. We evaluate MFLAMA through extensive simulations and quantify the improvement in channel utilization through the use of multiple channels. Our results indicate that as we increase the number of orthogonal channels used for communication, there is significant improvement in channel utilization and queueing delay. However, we notice a ldquodiminishing returnsrdquo effect as we increase the number of channels, i.e., the performance improvements observed decrease with the number of channels beyond a certain threshold. This threshold depends on the topology and traffic flow patterns being used.

We present the design and performance of a new approach to packet switching for MANETs, which we call context aware protocol engines (CAPE). With CAPE, nodes disseminate information in the network by means of context-aware packet switching that enables the statistical multiplexing of bandwidth, processing and storage resources using integrated signaling covering channel access, routing and other functions, to share and store the context within which information is disseminated. Data packet headers consist of simple pointers to their context, and elections and opportunistic reservations integrated with routing are used to attain high throughput and low channel-access delay.

We consider the problem of routing messages through a network with episodic connectivity without a priori knowledge of node schedules or locations. We present Steward assisted routing (StAR), an efficient loop-free routing framework that can operate in networks that are well-connected as well as in networks that exhibit intermittent connectivity; the proposed protocol uses Steward nodes to deliver data to destinations that may be partitioned from the source. We also introduce a companion protocol, scoped contact and interest propagation (SCIP), which contains mechanisms with which dissemination of routing control information for destinations of interest is scoped to a well-defined region of the network. We evaluate our protocols through simulations with four distinct mobility scenarios, including two that are generated using data traces from real networks. Our results show that StAR achieves delivery rates comparable to epidemic routing with far less signaling overhead. We also show that the addition of SCIP to StAR reduces route maintenance overhead significantly without impacting delivery rates.

Many multipath routing protocols proposed to date have used destination sequence numbers to provide multiple loop-free paths to destinations. We present the first on-demand multipath routing protocol for ad hoc networks that uses source sequence numbers to maintain loop-free routes. We propose a novel load-balancing scheme that incurs very little control overhead. Extensive simulations illustrate that the proposed multipath protocol performs better than single-path approaches and that the proposed load-balancing scheme performs better than basic round-robin scheduling.

We propose the distributed channel access scheduling using virtual MIMO protocol (CHAMP). In CHAMP, nodes build a channel schedule in a distributed fashion to utilize the spatial multiplexing gain of virtual MIMO links. We also use a cooperative relay strategy to fully utilize the available degrees of freedom of virtual antenna arrays. We analyze the single-hop saturation throughput of CHAMP and evaluate its multi-hop performance through simulation. The results show that CHAMP can achieve better performance than a contention-based MAC protocol using MIMO links.

We introduce a collaboration-driven approach to the sharing of the available bandwidth in wireless ad hoc networks, which we call many-to-many cooperation, that allows concurrent many-to-many communication. This scheme is based on the integration of multi-user detection and position-location information with frequency and code division in mobile ad hoc networks (MANETs). Transmissions are divided in frequency and codes according to nodal locations, and successive interference cancellation (SIC) is used at receivers to allow them to decode and use all transmissions from strong interfering sources. Consequently, the interference is divided into constructive interference (COI) and destructive interference (DEI). We show that, if each node is allowed to expand its bandwidth, both the link's Shannon capacity and the per source-destination throughput scale likeO(nalpha/2) (upper-bound) and Omega[f(n)] (lower-bound), for n nodes in the network, a path loss parameter alpha > 2, and 1 les f(n)alpha/2. Many-to-many cooperation allows multi-copy relaying of the same packet, which reduces the packet delivery delay compared to single-copy relaying without any penalty in capacity.

We propose the topology-aware hybrid channel access using virtual MIMO protocol (THAMP). In THAMP, nodes build the channel schedule in a distributed fashion based on the topology information and utilize different antenna gains of virtual MIMO links. Through the joint utilization of spatial diversity gain and spatial multiplexing gain at different nodes, THAMP increases the spatial reuse of the system and reduces the possible collisions of control packets. Simulation results show that THAMP can achieve a better performance than a contention-based MAC protocol using MIMO links.

The protocols used in ad hoc networks today are based on the assumption that the best way to approach multiple access interference (MAI) is to avoid it. Unfortunately, as the seminal work by Gupta and Kumar has shown, this approach does not scale. We demonstrate that protocol architectures that exploit multi-packet reception (MPR) do increase the order of the transport capacity of random wireless ad hoc networks for multi-pair unicast applications by a factor of Θ(log n) and Θ(log (log n)) under the protocol and physical models, respectively, where n is the number of nodes in the network. By contrast, Liu, Goeckel, and Towsley have shown that network coding (NC) does not increase the order capacity of wireless ad hoc networks under the protocol and physical models.

This paper introduces a scheduled-access, multi-channel medium access control (MAC) framework for wireless multi-hop ad hoc networks (MANETs). The proposed framework dubbed dynamic multi-channel medium access, or DYNAMMA, features: (1) ability to dynamically adapt to application-specific traffic patterns, (2) collision-free, multi-channel operation, (3) energy efficiency, and (4) minimum signaling overhead. We evaluate DYNAMMA through extensive simulations and compare its performance against scheduled-access (e.g., TRAMA) and contention-based (e.g., 802.11) MAC protocols for different application scenarios. Our results show that DYNAMMA's ability to perform collision-free transmission over multiple channels significantly increases system capacity through higher channel utilization and spatial re-use. When compared to TRAMA, DYNAMMA's efficiency in terms of signaling overhead yields considerable energy savings as well as queueing delay reduction. We also present an implementation of DYNAMMA over an Ultra-Wideband (UWB) radio testbed. Our UWB testbed results indicate that DYNAMMA can achieve both high channel utilization (close to 90% for our experiments) and high energy efficiency (nodes, on average, sleep one third of the time).

rdquoThe paper presents a mathematical framework for quantifying the overhead of proactive routing protocols in mobile ad hoc networks (MANETs). We focus on situations where the nodes are randomly moving around but the wireless transmissions can be decoded reliablely, when nodes are within communication range of each other. We explicitly present a framework to model the overhead as a function of stability of topology and analytically characterize the statistical distribution of topology evolutions. The OLSR protocol is further singled out for a detailed analysis, incorporating the proposed analytical model. Results are compared against Qualnet simulations for random movements, which corroborate the essential characteristics of the analytical results. The key insight that can be drawn from the analytical results of this paper is that nodal movements will drive up the overhead by a penalty factor, which is a function of the overall stability of the network.

The protocols used in ad hoc networks today are based on the assumption that the best way to approach multiple access interference (MAI) is to avoid it. Unfortunately, as the seminal work by Gupta and Kumar has shown, this approach does not scale. Recently, Ahlswede, Ning, Li, and Yeung showed that network coding (NC) can attain the max-flow min-cut throughput for multicast applications in directed graphs with point-to-point links. Motivated by this result, many researchers have attempted to make ad hoc networks scale using NC. However, the work by Liu, Goeckel, and Towsley has shown that NC does not increase the order capacity of wireless ad hoc networks for multi-pair unicast applications. We demonstrate that protocol architectures that exploit multi-packet reception (MPR) do increase the order capacity of random wireless ad hoc networks by a factor Θ(log n) under the protocol model. We also show that MPR provides a better capacity improvement for ad hoc networks than NC when the network experiences a single-source multicast and multi-pair unicasts. Based on these results, we introduce design problems for channel access and routing based on MPR, such that nodes communicate with one another on a many-to-many basis, rather than one-to-one as it is done today, in order to make ad hoc networks truly scalable.

Multiuser diversity has been shown to increase the throughput of mobile ad hoc wireless networks (MANETs) when compared to fixed wireless networks. This paper addresses a multiuser diversity strategy that permits one of multiple one-time relays to deliver a packet to its destination. We show that the throughput of the original single one-time relay strategy is preserved by our multi-copy technique. The reason behind achieving the same asymptotic throughput is the fact that, as we demonstrate in this paper, interference for communicating among closest neighbors is bounded for different channel path losses, even when goes to infinity. We show that a significant delay reduction is possible by multi-copy relaying when is finite. Furthermore, we find that the average delay and delay variance for both the one and multi-copy relay strategies scale like and , respectively. We derive an approximation of the delay for multi-copy forwarding scheme and demonstrate that this approximation is very close to simulation results in MANET systems.

This paper presents the first analytical model of wireless ad hoc networks that considers the impact of realistic antenna-gain patterns on network performance. As such, our modeling approach allows the study of ad hoc networks in which nodes are equipped with directional antennas. This modeling capability stands out from all previous analytical models, which have only dealt with omnidirectional or over-simplified antenna gain patterns, and which have not addressed the specific mechanisms of the medium access control (MAC) protocols used (e.g., the backoff mechanism). A new analytical model for the IEEE 802.11 DCF MAC is introduced that allows the study of different carrier-sensing mechanisms, such as the directional virtual carrier sensing (DVCS) protocol that we use to validate our analytical model and show its applicability. Our numerical results show that our new analytical model predicts the results obtained by discrete-event simulations very accurately, and does it with a processing time that is orders of magnitude faster than the time required by simulations.

We propose a new hop-by-hop routing protocol for ad hoc wireless networks that uses a novel sequence number scheme to ensure loop-freedom at all times.We use a single large per-destination label space to order nodes in a topological sort (directed acyclic graph).Nodes manipulate the label set innetwork without needing destination-controlled resets, so path repair is localized.The label size is large enough that it should never be exhausted in the lifetime of any given network.Route request flooding is performed through a new method that exploits the inherent partial order of the network, so nodes can share RREQ floods.Whereas most previous route request pruning techniques create a request tree, the new technique creates a directed acyclic request graph.Simulation results compared to AODV, DSR and OLSR show that the new protocol has in most cases equivalent or better packet delivery ratio and latency, but with a fraction of the network load.

We introduce a new communication scheme for mobile wireless ad hoc networks (MANETs) utilizing the concept of cooperative many-to-many communication, called opportunistic cooperation1, as opposed to the traditional approach that emphasizes on point-to-point communication. In the new paradigm, the adjacent nodes no longer interfere with each other but rather cooperate. Our analysis is for MANETs when all the nodes in the network are endowed with M antennas. We derive two upper bounds on the ergodic capacity per node in the network. These upper bounds are compared with Monte-Carlo simulation of point-to-point and many-to-many communications. We show that one of our upper bounds is a tight bound. Also, we demonstrate that the capacity of MANETs with multiple antennas is improved significantly using cooperation as compared to non-cooperative schemes, i.e., point-to-point communication.

We introduce a medium access control protocol for ad hoc networks. The new protocol, which we call ORMA (opportunistic reservation multiple access) is aimed at providing both high throughput and bounded channel access delays, which are critical for supporting integrated voice and data services over ad hoc networks. In ORMA, the channel is divided into a random access section and a scheduled access section. The first is used to exchange neighborhood information, the latter is used for data transmissions over time slots organized in frames, with each time slot being accessed through reservations or probabilistic elections. To attain high throughput, nodes access data slots based on a fair election in which they win with a certain probability. To attain bounded channel access delays, nodes reserve time slots by using a novel opportunistic reservation. The performance of ORMA is studied by both analysis and simulations. It is also compared against the performance of schemes based entirely on probabilistic or fixed conflict-free slot assignment

We present a new protocol for collision-free channel access in ad hoc networks called Bid Activation Multiple Access (BAMA). BAMA is based on bids made by nodes for slots within the context of probabilistic channel access. Winners of the bids for a given slot are determined as a result of a fair election of the bids for that slot. Nodes attempt to acquire varying number of slots depending on their traffic requirements. Nodes transmit their schedule information once in each frame prior to the data packet transmission in the slots acquired by them. Mismatched schedule information for a given slot are corrected based on the same fair election by the nodes that hear the schedule information. BAMA does not require explicit control information (HELLO packets) to build up local or global topology of the nodes to compute a transmission schedule for the nodes. The performance of BAMA is studied by simulations and compared against the performance of comparable protocols. It is found that BAMA provides better throughput and much lower end to end delay when compared to other protocols, both at low loads as well as high loads. The traffic adaptive nature of BAMA allows for the performance of BAMA to be largely independent of the network load. This makes it ideal for deployment in high bandwidth scenarios where low end to end delay is desirable.

Capacity improvement is one of the major challenges in the design of mobile ad hoc networks. Use of multiple channels is a useful technique in order to achieve capacity improvement by allowing nodes that need to exchange data to operate on the same channel and nodes that do not need to exchange data to operate on different channels. In the recent past some research has been done in the area of improving channel capacity using multiple channels for unicast flows. However we are not aware of any prior work for improving the channel capacity for multicast flows. We present the cross layer ad hoc multiple channel multicasting protocol (CLAMMP) for mobile ad hoc networks (MANET's). CLAMMP is the first protocol for MANET's which uses multiple channels to increase capacity for multicasting flows. CLAMMP is a cross-layered protocol in the sense that it traverses both the routing as well as the MAC layers. Using simulations in Qualnet 3.5, we compare CLAMMP with PUMA (tree-mode) and ODMRP, which are representatives of mesh-based and tree-based multicast routing in ad hoc networks. The results from a wide range of scenarios show that CLAMMP improves network capacity by an order of magnitude compared to the other two protocols

Multi-constrained path (MCP) selection, in which the key objective is to search for feasible paths satisfying multiple routing constraints simultaneously, is known to be an NP-Complete problem. Multi-constrained path optimization (MCPO) is different from MCP mainly in that, the feasible paths selected should also be optimal with regard to an optimization metric, which makes path computation in MCPO even harder.We propose a fully distributed multi-constrained path optimization routing (MPOR) protocol that solves the general k-constrained path selection and routing optimization problems. MPOR computes paths using distance vectors exchanged only amongst neighboring nodes and does not require the maintenance of global network state about the topology or resources; supports hop-by-hop, connectionless routing of data packets, and implements constrained path optimization by distributively constructing an x-optimal path set (i.e., the shortest, the second shortest and up to the xth shortest path in terms of the optimization metric) for each destination at each node. Simulations show that MPOR has satisfactory routing success ratios for multi-constrained path selection, and performs consistently with varying number of constraints. For constrained path optimization, MPOR has high probabilities of finding feasible paths that are also optimal or near-optimal for the given optimization metric.

This paper presents the first analytical model for ad hoc networks equipped with multiple-input multiple-output (MIMO) radios using space-time coding (STC) that considers the impact of the underlying radio-based topology on network performance. In particular, we consider the space-time block coding (STBC) technique known as the “Alamouti scheme.” We derive the effective signal-to-interference-plus-noise density ratio (SINR) of the Alamouti scheme under multiple access interference (MAI), and we propose the moment generating function (MGF) method to derive closed-form expressions for its symbol error probability under different modulation schemes when fading paths are independent but not necessarily identically distributed. The impact of the Alamouti scheme on IEEE 802.11 ad hoc networks is studied by introducing a new analytical model for the IEEE 802.11 DCF MAC. The model we introduce takes into account the impact of errors in both control and data frames, the carrier-sensing activity, and the finite-retry limit of frame retransmissions. Both PHY- and MAC-layer analytical models are incorporated into our previously-designed, general analytical model for ad hoc networks based on interference matrices. We apply the Alamouti scheme to different antenna system configurations and compare their performance with respect to the basic single-input-single-output (SISO) IEEE 802.11 DCF MAC.

Applications that require the communication of multiple video streams can consume considerable bandwidth and computing resources, which poses a challenge for the widespread use of videoconferencing over the IP Internet. On the one hand, the bandwidth of the link connecting a given participant to a videoconferencing session may not be enough to support many video streams at bit rates of 500 kbps or more, especially when the participant is connecting to the rest of the Internet through a wireless link. On the other hand, the processing capacity of a participating site may not be enough to decode several video streams in real time. This paper explores the use of floor control over videoconferencing applications as a means to support videoconferences with many participating sites, but with a processing and communication overhead per site that is equivalent to a two-party videoconference. The main tradeoff we explore is the scalability attained with floor control versus the latencies incurred with floor transitions, which can be much too disruptive to the videoconference participants. We present a viable compromise in which only the video stream of the "floor holder" is sent to all sites, but the floor-passing protocol is such that it supports a brief overlap of the transmissions from the old and the new floor holder, such that the participants in the videoconference can instantaneously switch over to the media streams of the next speaker in an apparently seamless transition. Experimental results and implementation in a research video-conferencing system show that the proposed protocol can run effectively, eliminating race conditions, while maintaining scalability and reliability

We show that the way in which the ad-hoc on-demand distance vector (AODV) protocol handles destination-based sequence numbers can lead to looping of data packets, defacto network partitions, and counting to infinity in the presence of link or node failures in ad hoc networks using an unreliable medium access control (MAC) protocol like the IEEE 802.11 DCF (distributed coordination function). The source of AODV's problems with sequence numbers is the use of a delete period after which nodes are allowed to forget invalid routes to destinations. We present a new approach for the handling of sequence numbers in AODV that eliminates the use of delete periods for destination-based sequence numbers, and show, with simulation experiments, that the new approach performs the same as or better than AODV.

Symmetric cryptographic primitives are preferable in designing security protocols for mobile ad hoc networks (MANETs) because they are computationally affordable for resource-constrained mobile devices forming a MANET. Most proposed key-distribution and key-agreement schemes for symmetric cryptosystem assume services from on-line centralized authorities, or require the interaction between communicating parties. However, the presence of a centralized authority violates the ad hoc definition of MANETs, and interactive schemes require the routing of the ad hoc network to be established before the key agreement, which is difficult to ensure in a mobile ad hoc network (MANET). We propose a new non-interactive key agreement and progression (NIKAP) scheme for MANETs, which does not require an on-line centralized authority, can establish and update pairwise shared keys between any two nodes in a non-interactive manner, is configurable to operate synchronously (S-NIKAP) or asynchronously (A-NIKAP), and is able to provide differentiated security services w.r.t. specified security policies. As the name implies, NIKAP is especially valuable to scenarios in which shared secret keys are desired to be computed without negotiation between nodes over insecure channels, and need to be updated frequently

We introduce FLAMA (flow-aware medium access), an energy-efficient medium-access control (MAC) protocol designed for wireless sensor networks. FLAMA achieves energy efficiency by preventing idle listening, data collisions and transmissions to a node that is not ready to receive packets. It adapts medium access schedules to the traffic flows exhibited by the application. FLAMA is simple enough so that it can be run by nodes with limited processing, memory, communication, and power capabilities. We evaluate the performance of FLAMA through simulations and test-bed experimentation. Simulation results indicate that, in terms of reliability, queuing delay and energy savings, FLAMA outperforms TRAMA, the first traffic-adaptive, schedule-based MAC proposed for sensor networks, and S-MAC, a contention-based energy-efficient MAC. FLAMA achieves significantly smaller delays (up to 75 times) when compared to TRAMA with significant improvement in energy savings and reliability, demonstrating the importance of application awareness in medium access scheduling. Our simulation and test-bed results show that FLAMA achieves better end-to-end reliability with significant energy savings compared to S-MAC.

In any on-demand routing protocol, sources flood route requests (RREQ) to build routes to destinations, and each new RREQ is identified uniquely with a source-sequenced label (SSL) consisting of the source identifier and a locally generated sequence number. As a RREQ propagates, it creates a directed acyclic graph (DAG), because nodes relay each RREQ only once. We present the first framework for loop-free on-demand routing in ad hoc networks that is based directly on SSLs, rather than on independent mechanisms, which has been the way in which prior on-demand routing protocols have been designed. Extensive simulation results for simple protocol instantiations of our new framework operating in scenarios with 50 and 100-nodes under different traffic patterns show that our new protocols outperform AODV (Ad hoc on demand distance vector), DSR (dynamic source routing), and OLSR (optimized link state routing)

Multicast routing protocols based on shared trees employ one or more rendezvous points (usually called cores) for coordination. To address fault tolerance in case of core failure, multiple cores can be deployed. The location of cores is crucial for the performance of the protocol. In this context, the problem of finding the location for the cores is similar to the (k, r)-predominating set problem, (k, r)-DS, in graph theory. That is, (k, r)-DS is defined as the problem of selecting a subset of nodes D such that the remaining nodes are within distance r from at least k nodes in D. In mobile ad hoc networks (MANETs), finding the location of cores should be computed distributively, because the topology may change frequently. We present a distributed solution to the (k, r)-DS problem, named DKR, which is used for core selection in a novel multicast protocol named core hierarchical election for multicasting in ad hoc networks (CHEMA). CHEMA is designed to operate in the context of multiple channels and multiple interfaces. One interface is dedicated for the communication among cores and members, using a non-interfering channel. The performance of CHEMA is compared against one of the best performing multicast protocols to date. CHEMA is shown to perform better in all scenarios considered

We present the Protocol for multicasting over directional antennas (MODA) for mobile ad hoc networks (MANET). MODA is the first protocol for MANET's that uses directional antennas to reduce data packet overhead. Without increasing energy consumption, MODA increases the range of transmission as a result of which fewer nodes are involved in the forwarding process, which results in a reduction in data packet overhead. Using simulations in Qualnet 3.5, we compare MODA with PUMA and ODMRP. The results from a wide range of scenarios of varying mobility, group members, number of senders, traffic load, and number of multicast groups show that MODA attains comparable packet delivery ratios to ODMRP and PUMA, while incurring far less overhead

An extended depth-first-search (EDFS) algorithm is proposed to solve the multi-constrained path (MCP) problem in quality-of-service (QoS) routing, which is NP-Complete when the number of independent routing constraints is more than one. EDFS solves the general k-constrained MCP problem with pseudo-polynomial time complexity O(m2middot EN + N2), where E and N are the number of links and nodes of a graph respectively, and m is the maximum number of feasible paths maintained for each destination. This is achieved by deducing potential feasible paths from knowledge of previous explorations, without re-exploring finished nodes and their descendants in the process of the DFS search. One unique property of EDFS is that the tighter the constraints are, the better the performance it can achieve, w.r.t. both time complexity and routing success ratio. Analysis and extensive simulation are conducted to study the performance of EDFS in finding feasible paths that satisfy multiple QoS constraints. The main results show that EDFS is insensitive to the number of constraints, and outperforms other popular MCP algorithms when the routing constraints are tight or moderate. The performance of EDFS is comparable with that of the other algorithms when the constraints are loose

We present path verification routing (PVR) to enable robust, instantaneous on-demand loop-free routing of data packets based on their destination address in mobile ad hoc networks. PVR attains instantaneous loop-freedom by using a path verification technique without the necessity for sequence numbers, source-routed data packets, or nodal synchronization. The motivation for PVR is twofold. On the one hand, DSR provides loop-free routing but requires source routed data packets. On the other hand, AODV, which is based on destination-based sequence numbers, is vulnerable to the counting-to-infinity problem and has route requests that in many cases must be answered by the destinations. Simulation experiments are used to show that the performance of PVR is comparable to or better than that of AODV, AODVbis, DSR and OLSR.

Three-hop horizon pruning (THP) is an algorithm for computing a two-hop connected dominating set (TCDS) of the network, and has been shown to be more efficient than all prior distributed broadcasting mechanisms when a TCDS is preferred over a connected dominating set (CDS). However, like all other algorithms that depend on local topology information, THP is not reliable when the topology changes frequently. We describe and analyze the three-hop horizon enhanced pruning (THEP), which eliminates THP's limitations. First THEP adopts a virtual radio range (VR) that is shorter than the physical radio range (RR), and considers as one-hop neighbors only those nodes within VR. The gap between VR and RR works as a buffer zone in which nodes can move without loss of connectivity. Second, upon receiving a broadcast packet, the forwarder list in the packet header is analyzed together with the current information about the local neighborhood. Based on this, a node using THEP may decide to broadcast a packet even though it has not been selected as a forwarder by the sender. We conduct extensive simulations and show that AODV-THEP attains better performance than AODV in terms of delivery ratio, control overhead, packet collisions, and end-to-end delay.

We present the on-demand link vector (OLIVE) protocol, a routing protocol for ad hoc networks based on link-state information that is free of routing loops and supports destination-based packet forwarding. Routers exchange routing information reactively for each destination in the form of complete paths, and each node creates a labeled source graph based on the paths advertised by its neighbors. A node originates a broadcast route request (RREQ) to obtain a route for a destination for which a complete path does not exist in its source graph. When the original path breaks, a node can select an alternative path based on information reported by neighbors, and a node can send a unicast RREQ to verify that the route is still active. A node that cannot find any alternate path to a destination sends route errors reliably to those neighbors that were using it as next hop to the destination. Using simulation experiments in ns2, OLIVE is shown to outperform dynamic source routing, ad hoc on-demand distance vector, optimized link-state routing protocol, and topology broadcast based on reverse-path forwarding, in terms of control overhead, throughput, and average network delay, while maintaining loop-free routing with no need for source routes.

Multiuser diversity has been shown to increase the throughput of mobile ad hoc wireless networks (MANET) when compared to fixed networks. We present a different multiuser diversity strategy for packet relaying, which permits more than one-copy (multi-copies) of a packet to be received by relay nodes, thus allowing us to decrease the delay on such networks for a fixed number of total users n. We show that the /spl theta/(1) throughput is preserved by our multi-copy technique when n goes to infinity. In addition, we find that the average delay and variance scale like /spl theta/(n) and /spl theta/(n/sup 2/) respectively for both one-copy and multi-copies techniques. We also show that for a fixed n and by multi-copy forwarding, a maximum bounded delay value can he guaranteed.

We present a new protocol for collision-free channel access in ad hoc networks called the node activation with polling access (NAPA) protocol. NAPA assumes a time-slotted channel and operates by having each node elect a transmitting node for each time slot based on the identifiers of the nodes in its two-hop neighborhood. In contrast to prior topology-dependent transmission scheduling schemes (e.g., node activation multiple access, or NAMA) in which time slots are wasted when nodes selected for transmission have no packets to send, NAPA complements the election of nodes by means of polling and carrier sensing to use time slots allocated to nodes with no data to send. When a node elected for transmission has no packets to send, it polls one or multiple one-hop neighbors, and each neighbor determines if it can transmit during the time slot based on the identifiers of its two-hop neighbors and sensing of the channel. We show that NAPA supports collision-free transmissions, and compare its performance against NAMA.

This paper presents an analytical model to predict energy consumption in saturated IEEE 802.11 single-hop ad hoc networks under ideal channel conditions. The model we introduce takes into account the different operational modes of the IEEE 802.11 DCF MAC, and is validated against packet-level simulations. In contrast to previous works that attempted to characterize the energy consumption of IEEE 802.11 cards in isolated, contention-free channels (i.e., single sender/receiver pair), this paper investigates the extreme opposite case, i.e., when nodes need to contend for channel access under saturation conditions. In such scenarios, our main findings include: (1) contrary to what most previous results indicate, the radio's transmit mode has marginal impact on overall energy consumption, while other modes (receive, idle, etc.) are responsible for most of the energy consumed; (2) the energy cost to transmit useful data increases almost linearly with the network size; and (3) transmitting large payloads is more energy efficient under saturation conditions

We present a new class of on-demand routing protocols called split label routing (SLR). The protocols guarantee loop-freedom at every instant by ensuring that node labels are always in topological order, and thus induce a directed acyclic graph (DAG). The novel feature of SLR is that it uses a dense ordinal set with a strict partial order to label nodes. For any two labels there is always some label in between them. This allows SLR to "insert" a node in to an existing DAG, without the need to relabel predecessors. SLR inherently provides multiple paths to destinations. We present a practical, finitely dense implementation that uses a destination-controlled sequence number. The sequence number functions as a reset to node ordering when no more label splits are possible. The sequence number is changed only by the destination. Simulations show that our proposed protocol outperforms existing state-of-the-art on-demand routing protocols.

We present the on-demand link vector (OLIVE) protocol, a routing protocol for ad-hoc networks based on link-state information that is free of routing loops and supports destination-based packet forwarding. Routers exchange routing information reactively for each destination in the form of complete paths, and each node creates a labeled source graph based on the paths advertised by its neighbors. A node originates a broadcast route request to obtain a route for a destination for which a complete path does not exist in its source graph. When the original path breaks, a node can select an alternative path based on information reported by neighbors, and a node can send a unicast route request to verify that the route is still active. A node that cannot find any alternate path to a destination sends route errors reliably to those neighbors that were using it as next hop to the destination. Using simulation experiments in ns2, OLIVE is shown to outperform DSR, AODV, OLSR and TBRPF, in terms of control overhead, throughput, and average network delay, while maintaining loop-free routing with no need for source routes.

We examine on-demand multicasting in ad hoc networks. We study a wide range of simulation scenarios and identify key limitations of MAODV. Based on our findings, we propose a number of changes in MAODV, and call the resulting protocol robust multicasting in ad hoc networks using trees (ROMANT). We compare ROMANT to MAODV and ODMRP, for a wide range of simulation scenarios. Our results indicate that ROMANT effectively eliminates the limitations of MAODV. Moreover, it provides comparable or better packet delivery ratio than ODMRP at only a fraction of the overhead incurred by ODMRP.

We present the dynamic incremental routing (DIR) protocol, which features instantaneous loop-free routing of data packets based on their destination addresses (hop-by-hop routing). Loop-free routes are maintained by using "feasible distances" to order the nodes with respect to a destination. Simulation results show that the performance of DIR is much better than the performance of AODV, DSR and OLSR, which are indicative of the state of the art in routing protocols.

Protocols for sensor networks have traditionally been designed using the best effort delivery model. However, there are many specific applications that need a reliable data dissemination protocol. We present a protocol for efficient and reliable data delivery to all sensor nodes in an energy-constrained, event-driven sensor network in which nodes are mobile or static. The new protocol, SPROID (Scalable Protocol for RObust Information Dissemination), identifies data generated by a unique tag, uses content tables for faster dissemination of information and guarantees reliable dissemination to all nodes in the network within a finite time. SPROID can be made to work with any kind of physical layer requirements, but we focus on the case of a single-channel broadcast medium. Simulations results show that SPROID achieves complete data dissemination in shorter time and with more energy efficiency than SPIN (sensor network protocols using information negotiation).

We present and verify SMLDR (Shortest Multipath Labeled Distance Routing), an on-demand loop free multipath routing protocol. It extends Labeled Distance Routing (LDR) to the multipath domain and enables loop freedom by maintaining the ordering of distance invariants. By modifying the route update conditions of LDR and by using the concept of limiting distance we demonstrate shortest multipath routing. Further we describe the fundamental multipath concepts for on-demand routing protocols and elucidate how SMLDR exercises each of these concepts in its routing mechanisms. The performance of SMLDR is compared against the performance of LDR, AODV and its multipath variant AOMDV. The simulation results corroborate the need for shortest multipath routing in terms of higher performance for the chosen metrics.

A generalized framework for loop-free routing based entirely on destination sequence numbers is presented. The framework eliminates the counting-to-infinity problem found in AODV and other on-demand routing protocols based on destination sequence numbers. The sequence-number window routing (SWR) protocol is presented as an example of this framework. SWR is compared via simulations with DSR, AODV and OLSR using networks of 50 and 100 mobile nodes; the results indicate that SWR is as efficient as AODV without incurring counting to infinity.

We introduce the three-hop horizon pruning (THP) algorithm to make broadcast operations more efficient in ad hoc networks using contention-based MAC protocols. THP builds a two-hop connected dominating set (TCDS) of the network, which is a set of nodes such that every node in the network is within two hops from some node in the dominating set. Efficiency of broadcast operations is attained by implementing forwarding schemes that take advantage of a TCDS. More specifically, every node provides its one-hop neighbors with a list specifying one or more tuples, each with the identifier of a one-hop neighbor and a bit indicating if that neighbor dominates any two-hop neighbor. To forward a broadcast packet, a node tries to obtain the smallest subset of forwarders, which are one-hop neighbors that use some of the node's two-hop neighbors to reach any node that is three hops away. After such a selection of forwarders, the node broadcasts its packet with a header specifying the list of forwarders, and each forwarder in turn repeats the process.

We present the protocol for unified multicasting through announcements (PUMA) in ad-hoc networks, which establishes and maintains a shared mesh for each multicast group, without requiring a unicast routing protocol or the preassignment of cores to groups. PUMA achieves a high data delivery ratio with very limited control overhead, which is almost constant for a wide range of network conditions. Using simulations in Qualnet 3.5, we compare PUMA with ODMRP and MAODV, which are representatives of mesh-based and tree-based multicast routing in ad hoc networks. The results from a wide range of scenarios of varying mobility, group members, number of senders, traffic load, and number of multicast groups show that PUMA attains higher packet delivery ratios than ODMRP and MAODV, while incurring far less control overhead.

A new modeling framework is introduced for the analytical study of medium access control (MAC) protocols operating in multihop ad hoc networks. The model takes into account the effect of physical-layer parameters on the success of transmissions, the MAC protocol on the likelihood that nodes can access the channnel, and the connectivity of nodes in the network. A key feature of the model is that nodes can be modeled individually, i.e., it allows a per-node setup of many layer-specific parameters. Moreover, no spatial probability distribution or a particular arrangement of nodes is assumed; the model allows the computation of individual (per-node) performance metrics for any given network topology and radio channel model. To show the applicability of the modeling framework, we model multihop ad hoc networks using the IEEE 802.11 distributed coordination function and validate the results from the model with discrete-event simulations in Qualnet. The results show that our model predicts results that are very close to those attained by simulations, and requires seconds to complete compared to several hours of simulation time.

We present the Feasible Label Routing (FLR) protocol for mobilead hoc networks, which uses path information to establish routes to destinations on demand. FLR enables loop-free incremental(hop-by-hop) routing of data packets using only the addresses of their destinations. Like the dynamic source routing (DSR) protocol, FLR avoids the need for any time-stamps or sequence numbers by the use of path vectors exchanged when routes are established or repaired. Instantaneous loop freedom is attained by using path information for a destination as labels with which routers are ordered lexicographically with respect to the destination, i.e., FLR ensures that the labels of routers for a given destination become "smaller" the closer they are to the destination. Simulation experiments in Qualnet show that the performance of FLR is far better than the performance of the ad-hoc on-demand distance vector (AODV) protocol, the dynamic source routing (DSR) protocol, and the optimized link state routing (OLSR) protocol, in terms of the packet delivery ratio and average delivery latencies achieved, as well as the overhead incurred in the network.

The inclusion of multiple metrics in a routing computation is called policy-based routing. Previous work on solutions to this problem have focused on virtual-circuit-based solutions, and have resulted in computationally expensive algorithms. This paper presents a number of advances in the provision of policy-based routing services in networks and internetworks. An integrated policy-based routing architecture is formulated where the general problem is decomposed into a traffic engineering problem of computing routes in the context of administrative traffic constraints, and a quality-of-service (QoS) problem of computing routes in the context of performance-related path constraints. A family of routing algorithms are presented for computing routes in the context of these constraints which achieve new levels of computational efficiency. Lastly, a forwarding architecture is presented that efficiently supports hop-by-hop forwarding in the context of multiple paths to each destination, which is required for policy-based routing.

Multiuser diversity has been shown to increase the throughput of mobile ad-hoc wireless networks (MANET) when compared to fixed wireless networks. This paper addresses a multiuser diversity strategy that permits one of multiple one-time relays to deliver a packet to its destination. We show that the /spl theta/(1) throughput of the original single one-time relay strategy is preserved by our multi-copy technique. The reason behind achieving the same asymptotic throughput is the fact that, as we demonstrate in this paper, interference for communicating among closest neighbors is hounded for different channel path losses, even when n goes to infinity. We find that the average delay and its variance scale like /spl theta/(n) and /spl theta/(n/sup 2/), respectively, for both the one and multi-copy relay strategies. Furthermore, while for finite n the delay values in the single-copy relaying strategy are not bounded, our multi-copy relay scheme attains bounded delay.

An analytical model for single-hop ad hoc networks is introduced that considers the impact of the physical layer on the operation and performance of saturated IEEE 802.11. Using the bottom-up approach, aspects of the physical layer are explicitly incorporated in the dynamics of the events governing the operation of the IEEE 802.11 binary exponential backoff algorithm leading to a more realistic computation of the node's average service time and throughput. We study the impact of frequency-nonselective slowly time-variant Rician fading channels on the performance of single-hop ad hoc networks using the IEEE 802.11 distributed coordination function in saturation. We validate our model through simulations and study of the throughput performance of the four-way handshake mechanism under direct sequence spread spectrum (DSSS) with differential binary phase shift keying (DBPSK) modulation.

The use of dominating-set neighbor elimination as an integral part of the distribution of route requests using the ad hoc on-demand distance vector (AODV) protocol as an example of on-demand routing protocols is investigated. We use detailed simulations to show that simply applying dominant pruning (DP) to the distribution of route requests in AODV results in pruning too many route requests in the presence of mobility and cross-traffic. Accordingly, we introduce several heuristics to compensate the effects of DP and show that the resulting AODV with dominating set heuristics (AODV-DS) has comparable or better delivery ratio, network load, and packet latency than the conventional AODV. AODV-DS exhibits over 70% savings on RREQ traffic than conventional AODV, and in some situations, AODV-DS may have a lower control overhead using Hello packets than conventional AODV without Helios.

We explore the use of directional antennas to improve the performance of broadcasting in ad hoc networks. We investigate both the performance of unicast traffic in the presence of broadcast traffic and the performance of broadcast traffic when mixed with unicast traffic, which is different from previous investigations reported in the literature in which broadcast traffic is investigated in isolation. Through extensive simulation experiments with three MAC schemes, we show that throughput and delay can vary widely even in networks in which nodes are uniformly distributed. We also show that the use of a MAC protocol that utilizes directional antennas can help to improve the performance of broadcast traffic in ad hoc networks, in terms of both throughput and delay, through a more aggressive channel access scheme that maximizes spatial reuse.

This paper presents the history-based scheduling (HBS) protocol for collision-free channel access in ad hoc networks. In HBS, the channel is scheduled based on the history of activity of each node in order to attain higher channel utilization than traditional distributed scheduling schemes based on node activation. Conflict-free access to the channel is determined at each node based on a priority list of the nodes within two hops of each node that takes into account the activity history of each node. To keep the activity history of each node synchronized, a node that is assigned the channel and has no data packet to transmit simply transmits a "nothing-to-transmit" (NT) packet in that time slot. In this way, the exchange of the signal packet should be reduced. The throughput and delay characteristics of HBS are compared analytically and by simulation with those of CSMA/CA and the node activation multiple access (NAMA) protocol.

Dominant pruning (DP) is a distributed connected dominating-set algorithm that can be used for reducing the impact of flooding in wireless ad hoc networks. We propose an enhanced dominant pruning (EDP) approach to be used in the route discovery process of on-demand routing protocols. To show the benefits of EDP, we integrate EDP into the ad-hoc on-demand distance vector (AODV) protocol. We present detailed simulation results showing that our approach improves standard AODV in most aspects, and that it is simple and easy to implement. Our approach is compared against AODV and OLSR, as good representatives of on-demand and proactive routing for ad-hoc wireless networks.

Three collision-avoidance protocols are analyzed that use omni-directional packet reception together with omni-directional transmissions, directional transmissions, or a combination of both. A simple model is introduced to analyze the performance of these collision avoidance protocols in multi-hop networks with arbitrary topologies. The numerical results of this analysis show that collision avoidance using a narrow antenna beamwidth for the transmission of all control and data packets achieves the highest throughput among the three collision avoidance schemes considered. Simulation experiments of the popular IEEE 802.11 MAC protocol and its variants based on directional transmissions and omni-directional packet reception validate the results predicted in the analysis. The results further show that narrow-beamwidth transmissions can also reduce the average delay experienced by nodes. It is concluded that the advantage of spatial reuse achieved by narrow-beamwidth transmissions outweighs that of conservative collision avoidance schemes featured by the omnidirectional transmission of some control packets. This is due to the fact that the latter requires far more stringent coordination of nodes with their neighbors and hidden terminals, which can lead to much more channel resource wasted due to nodes' excessive waiting time.

This paper presents an analytical model to compute the average service time and jitter experienced by a packet when transmitted in a saturated IEEE 802.11 ad hoc network. In contrast to traditional work in the literature, in which a distribution is usually fitted or assumed, we use a bottom-up approach and build the first two moments of the service time based on the IEEE 802.11 binary exponential backoff algorithm and the events underneath its operation. Our model is general enough to be applied to any type of IEEE 802.11 wireless ad hoc network where the channel state probabilities driving a node's backoff operation are known. We apply our model to saturated single-hop ad hoc networks under ideal channel conditions. We validate our model through extensive simulations and conduct a performance evaluation of a node's average service time and jitter for both direct sequence and frequency-hopping spread spectrum physical layers.

This paper studies the fairness with which competing flows share the channel in ad hoc networks using collision avoidance protocols. It is shown that the required multihop coordination makes the backoff-based distributed fair queueing schemes less effective. Using extensive simulations of two competing flows with different underlying network configuration, it is shown that the commonly used flow contention graph is insufficient to model the contention among nodes and that various degrees of unfairness can take place. The fairness problem is more severe in TCP-based flows due to the required acknowledgment traffic, and TCP throughput is also negatively affected. A measurement based fair scheme is analyzed in which nodes estimate their fair share of the channel from overheard traffic and adjust their backoff window accordingly (voluntarily); it is shown that such a scheme achieves much better fairness but sacrifices too much throughput. These results indicate that more explicit information exchange among contending nodes is mandatory to solve the fairness problem conclusively while maintaining reasonable throughput.

The efficiency of a communication network depends not only on its control protocols, but also on its topology. We propose a distributed topology management algorithm that constructs and maintains a backbone topology based on a minimal dominating set (MDS) of the network. According to this algorithm, each node determines the membership in the MDS for itself and its one-hop neighbors based on two-hop neighbor information that is disseminated among neighboring nodes. The algorithm then ensures that the members of the MDS are connected into a connected dominating set (CDS), which can be used to form the backbone infrastructure of the communication network for such purposes as routing. The correctness of the algorithm is proven, and the efficiency is compared with other topology management heuristics using simulations. Our algorithm shows better behavior and higher stability in ad hoc networks than prior algorithms.

A new protocol is presented for on-demand loop-free routing in ad hoc networks. The new protocol, called labeled distance routing (LDR) protocol, uses a distance invariant to establish an ordering criterion and per-destination sequence numbers to reset the invariant resulting in loop-freedom at every instant. The distance invariant allows nodes to change their next hops or distances to destinations without creating routing-table loops. The destination sequence number, which only the destination may increment, permits nodes to reset the values of their distance invariants. The performance of LDR is compared against the performance of three other protocols that are representative of the state-of-the art, namely AODV, DSR and OLSR.

The traffic-adaptive medium access protocol (TRAMA) is introduced for energy-efficient collision-free channel access in wireless sensor networks. TRAMA reduces energy consumption by ensuring that unicast, multicast, and broadcast transmissions have no collisions, and by allowing nodes to switch to a low-power, idle state whenever they are not transmitting or receiving. TRAMA assumes that time is slotted and uses a distributed election scheme based on information about the traffic at each node to determine which node can transmit at a particular time slot. TRAMA avoids the assignment of time slots to nodes with no traffic to send, and also allows nodes to determine when they can become idle and not listen to the channel using traffic information. TRAMA is shown to be fair and correct, in that no idle node is an intended receiver and no receiver suffers collisions. The performance of TRAMA is evaluated through extensive simulations using both synthetic- as well as sensor-network scenarios. The results indicate that TRAMA outperforms contention-based protocols (e.g., CSMA, 802.11 and S-MAC) as well as scheduling-based protocols (e.g., NAMA) with significant energy savings.

A novel hybrid channel access scheme that combines sender-initiated collision-avoidance handshakes is proposed for multi-hop ad hoc networks. The new scheme is compatible with the popular IEEE 802.11 MAC protocol and involves adding very simple queue management and bookkeeping work mechanisms. Simulation experiments show that the new scheme can alleviate the fairness problems existing in applications running on either UDP or TCP with almost no degradation in throughput. More importantly, it is also shown that without explicit information exchange among nodes, the fairness problem cannot be solved conclusively.

Untethered nodes in mobile ad hoc networks strongly depend on the efficient use of their batteries. In this paper, we propose a new metric, the drain rate, to forecast the lifetime of nodes according to current traffic conditions. This metric is combined with the value of the remaining battery capacity to determine which nodes can be part of an active route. We describe new route selection mechanisms for MANET routing protocols, which we call the minimum drain rate (MDR) and the conditional minimum drain rate (CMDR). MDR extends nodal battery life and the duration of paths, while CMDR also minimizes the total transmission energy consumed per packet. Using the ns-2 simulator and the dynamic source routing (DSR) protocol, we compare MDR and CMDR against prior proposals for energy-aware routing and show that using the drain rate for energy-aware route selection offers superior performance results. Methods keywords are system design and simulations.

The quest for efficient medium access control (MAC) protocols for multi-hop ad hoc networks has aroused great interest in using directional antennas. Some MAC protocols using directional antennas have been proposed in the past; they trade off spatial reuse and collision avoidance via a combination of omnidirectional and directional transmission modes. It is argued that the benefit of spatial reuse achieved by a MAC protocol that uses a directional mode in all transmissions can outweigh the benefit of a conservative collision avoidance MAC protocol that sends some omni-directional control packets to silence potential interfering nodes. We present detailed simulation experiments of the popular IEEE 802.11 MAC protocol and its variants that make use of a directional transmission mode in sufficiently random networks. It is concluded that, in contention-based MAC protocols for multi-hop networks infested with hidden terminals, the aggressive channel access scheme featured by all-directional transmissions indeed outperforms other conservative schemes in terms of enhanced throughput and reduced delay.

We present a node-centric approach to hybrid routing for ad hoc networks in which normal nodes are distinguished from special nodes, called netmarks, hosting popular network services or functioning as points of attachment to the Internet. With node-centric hybrid routing, netmarks force other common nodes to maintain routing information for them by advertising their routing information as in table-driven routing protocols. Routes between peer nodes are set up on-demand. A node-centric routing solution is presented based on partial link state information. Simulation results using ns2 show that this approach performs much better than on-demand routing protocols.

Mobile ad hoc networks' (MANETs) inherent power limitation makes power-awareness a critical requirement for MANET protocols. We propose a new routing metric, the drain rate, which predicts the lifetime of a node as a function of current traffic conditions. We describe the minimum drain rate (MDR) mechanism which uses a combination of the drain rate with remaining battery capacity to establish routes. MDR can be employed by any existing MANET routing protocol to achieve a dual goal: extend both nodal battery life and connection lifetime. Using the ns-2 simulator and the dynamic source routing (DSR) protocol, we compared MDR to the minimum total transmission power routing (MTPR) scheme and the min-max battery cost routing (MM-BCR) scheme and proved that MDR is the best approach to achieve the dual goal.

Mobile wireless ad-hoc networks lack some basic abilities taken for granted in wired networks, such as the ability to know adjacent nodes. We present a neighbor discovery protocol, with particular application to broadcast flooding. The neighbor exchange protocol (NXP) has two main improvements over simple periodic broadcast schemes: (1) it only sends Hello packets when necessary to maintain topology and (2) uses sequence numbers in redistributed information to aid in convergence. In simulation, we compare NXP to a periodic protocol and simple flooding for all-node packet broadcasts and two dissemination techniques. We show that we maintain similar delivery rates while using fewer control packets in most configurations.

Traditional routing protocols based on link-state information form a network topology through the exchange of link-state information by flooding or by reporting partial topology information and compute shortest routes to each reachable destination using a path-selection algorithm like Dijkstra's algorithm or the Bellman-Ford algorithm. However, in an on-demand link-state routing protocol, no one node needs to know the paths to every other node in the network. Accordingly, when a node chooses a next hop for a given destination, it must be true that the next hop has reported a path to the same destination; otherwise, packets sent through that node would be dropped. We present a new path-selection algorithm that unlike traditional shortest path algorithms, computes shortest paths with the above on-demand routing constraint.

We present the hybrid activation multiple access (HAMA) protocol for ad hoc networks. Unlike previous channel access scheduling protocols that activate either nodes or links only, HAMA is a node-activation channel access protocol that also maximizes the chance of link activations using time- and code-division schemes. HAMA only requires identifiers for the neighbors within two hops from each node to schedule channel access. Using this neighborhood information, each node determines whether to transmit in the current time slot on a dynamically assigned spreading code. A neighbor protocol supplements HAMA with up-to-date two-hop neighborhood information by reliably propagating the one-hop neighbor updates through a novel random access technique. The throughput and delay characteristics of HAMA in randomly-generated multihop wireless networks are studied by analyses and simulations. The results of the analyses show that HAMA achieves higher channel utilization in ad hoc networks than a distributed scheduling scheme based on node activation, similar throughput as a well-known scheduling algorithm based on complete topology information, and much higher throughput than the ideal CSMA and CSMA/CA protocols.

The paper presents the first analytical model to derive the saturation throughput of collision avoidance protocols in multi-hop ad hoc networks with nodes randomly placed according to a two-dimensional Poisson distribution. We show that the sender-initiated collision-avoidance scheme performs much better than the ideal CSMA scheme with a separate channel for acknowledgments. More importantly, we show that the collision-avoidance scheme can accommodate much fewer competing nodes within a region in a network infested with hidden terminals than in those cases without hidden terminals or with just a few, if reasonable throughput is to be maintained. Simulations of the popular IEEE 802.11 MAC protocol show that it cannot ensure collision-free transmission of data packets and thus throughput can degrade well below what is predicted by the analysis of a correct collision avoidance protocol. Based on these results, a number of improvements are proposed for the IEEE 802.11 MAC protocol.

We study the performance of reliable and unreliable all-node broadcast over ad-hoc networks that use contention-based channel access. To obtain analytical results while preserving hidden-terminal and node clustering characteristics of ad-hoc networks, we introduce a novel differential-equation fluid model for information flow through a network of cluster trees, where a spanning tree joins groups of fully connected nodes. Through numerical analysis and simulations in GloMoSim, we show throughput, goodput, and loss rates for reliable and unreliable networks. For reliable broadcast, we also find NAK rates, NAK loss rates, and retransmission rates. We show that using end-to-end sequence numbers, which are common in reliable multicast, for NAK generation in ad-hoc networks creates substantial unnecessary traffic.

Directional antennas can adaptively select radio signals of interest in specific directions, while filtering out unwanted interference from other directions. Although a couple of medium access protocols based on random access schemes have been proposed for networks with directional antennas, they suffer from high probability of collisions because of their dependence on omnidirectional mode for the transmission or reception of control packets in order to establish directional links. We propose a distributed receiver-oriented multiple access (ROMA) channel access scheduling protocol for ad hoc networks with directional antennas, each of which can form multiple beams and commence several simultaneous communication sessions. Unlike random access schemes that use on-demand handshakes or signal scanning to resolve communication targets, ROMA determines a number of links for activation in every time slot using only two-hop topology information. It is shown that significant improvements on network throughput and delay can be achieved by exploiting the multi-beam forming capability of directional antennas in both transmission and reception. The performance of ROMA is studied by simulations, and compared with a well-know static scheduling scheme that is based on global topology information.

Article Share on Flow-oriented protocols for scalable wireless networks Author: J. J. Garcia-Luna-Aceves University of California, Santa Cruz, California University of California, Santa Cruz, CaliforniaView Profile Authors Info & Claims MSWiM '02: Proceedings of the 5th ACM international workshop on Modeling analysis and simulation of wireless and mobile systemsSeptember 2002 Pages 1–6https://doi.org/10.1145/570758.570759Online:28 September 2002Publication History 1citation486DownloadsMetricsTotal Citations1Total Downloads486Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We present source-tracing as a new viable approach to routing in ad-hoc networks where routers communicate the second-to-last hop and distance in preferred paths to destinations. We use two source-tracing algorithms, a table-driven protocol (BEST) in which routers maintain routing information for all destinations, and an on-demand routing protocol (DST) in which routers maintain routing information for only those destinations to whom they need to forward data. Simulation experiments are used to compare these protocols with DSR, which has been shown to incur less control overhead than other on-demand routing protocols. The simulations show that DST requires far less control packets to achieve comparable or better average delays and percentage of packet delivered than DSR, and that BEST achieves comparable results to DSR while maintaining routing information for all destinations.

Many routing protocols for ad hoc networks have been proposed to date. Among them, STAR (source tree adaptive routing protocol) is a representative table-driven protocol, while AODV (ad hoc on-demand distance vector protocol) and DSR (dynamic source routing protocol) are two representative on-demand protocols. This paper analyzes these three protocols using the GloMoSim simulation environment. The scenarios used in the simulation experiments take into account a variety of environmental factors that influence protocol performance. The performance of the protocols is compared in terms of their control overhead, amount of data delivered, and average latency in packet delivery. The simulation results show that STAR achieves better overall performance than AODV and DSR in sparsely connected networks. For the case of densely connected networks, AODV performs better in terms of data delivery, while STAR performs much better in terms of control overhead. The study also addresses the question of how accurate a simulator could be regarded for presenting the characteristics of the routing protocols and for comparison purposes.

The on-demand routing protocols that have been proposed to date use either path information (e.g., DSR) or distance information (e.g., AODV). We present SOAR, an on-demand link-state protocol based on partial link-state information in which a wireless router communicates to its neighbors the link states of only those links in its source tree that belong to the paths it chooses to advertise for reaching destinations with which it has active flows, SOAR does not require periodic link-state advertisements when there are no link connectivity changes in the network. Simulation studies for several scenarios of node mobility and traffic flows reveal that SOAR performs more efficiently than DSR, which is one of the best performing on-demand routing approaches based on path information.

The medium-access control (MAC) protocols for wireless networks proposed or implemented to date based on collision-avoidance handshakes between sender and receiver either require carrier sensing or the assignment of unique codes to nodes to ensure that intended receivers hear data packets without interference from hidden sources. We present and analyze a new collision-avoidance MAC protocol that we call receiver-initiated channel-hopping with dual polling (RICH-DP). RICH-DP is the first MAC protocol based on a receiver-initiated collision-avoidance handshake that does not require carrier sensing or the assignment of unique codes to nodes In order to ensure collision-free reception of data at the intended receivers in the presence of hidden terminals. The throughput and delay characteristics of RICH-DP is studied analytically, and extensive simulations are presented to verify the analysis and to present a more accurate prediction of how RICH-DP would operate in realistic scenarios. RICH-DP is applicable to ad-hoc networks based on commercial off-the-shelf frequency hopping radios operating in the unlicensed frequency bands.

Routing protocols using the distributed Bellman-Ford (DBF) algorithm converge very slowly to the correct routes when link costs increase, and in the case when a set of link failures results in a network partition, DBF simply fails to converge, a problem which is commonly referred to as the count-to-infinity problem. We present the first distance-vector routing algorithm, MDVA, that uses a set of loop-free invariants to prevent the count-to-infinity problem. MDVA, in addition, computes multipaths that are loop-free at every instant. In our earlier work we shows how such loop-free multipaths can be used in traffic load-balancing and minimizing delays, which otherwise are impossible to perform in current single-path routing algorithms.

Three types of collision-free channel access protocols for ad hoc networks are presented. These protocols are derived from a novel approach to contention resolution that allows each node to elect deterministically one or multiple winners for channel access in a given contention context (e.g., a time slot), given the identifiers of its neighbors one and two hops away. The new protocols are shown to be fair and capable of achieving maximum utilization of the channel bandwidth. The delay and throughput characteristics of the contention resolution algorithms are analyzed, and the performance of the three types of channel access protocols is studied by simulations.

A novel approach to source routing in ad hoc networks is introduced that takes advantage of maintaining information regarding the two-hop neighborhood of a node. The neighborhood aware source routing (NSR) protocol is presented based on this approach, and its performance is compared by simulation with the peformance of the Dynamic Source Routing (DSR) protocol. The simulation analysis indicates that NSR requires much fewer control packets while delivering at least as many data packets as DSR.

With on-demand routing, a router maintains routing information for only those destinations that need to be reached by the router. The approaches used to date to eliminate long-term or permanent loops in on-demand routing consist of obtaining complete routes to destinations dynamically, or obtaining only the next hops to destinations and validating the information using sequence numbers or internodal synchronization. We present a new approach to on-demand routing, which we call the DST (dynamic source tree) protocol. To eliminate looping, routers in DST communicate paths to destinations; however, only incremental updates to such paths are communicated by specifying the second-to-last hop and distance to each node in the subpath to the destination that must be updated. Simulation experiments are used to show that, in terms of control packet overhead, DST outperforms substantially the dynamic source routing (DSR) protocol which is arguably one of the most efficient on-demand routing approaches to date, while achieving similar performance in terms of the average delay and throughput of data packets.

A major concern with the IETF proposed integrated services (Intserv) architecture for providing quality of service is that the amount of reservation state it stores in the routers and the RSVP protocol it uses to maintain the consistency of reservation state may not be scalable to high-speed backbone networks. Because of the large number of flows in the backbone network, the refresh messages associated with RSVP's soft-state mechanism, apart from consuming memory, bandwidth and computing power, can experience significant queuing delays and prevent correct functioning of the soft-state mechanism. For the refresh mechanism to scale, therefore, the reservation state size must be bounded so that delays of time-sensitive refresh messages can also be bounded through adequate bandwidth allocation. Vutukury and Garcia-Luna-Accves (see. Proc. of ICCCN, 1999) described the scalable multipath aggregated routing architecture (SMART) In which the reservation state size is a function of number of destinations rather than number of flows in the network. In this paper, we describe a reservation protocol (AGREE) to maintain this reservation state aggregated along the multipaths. The AGREE protocol, like RSVP, uses soft-states, but also ensures that the refresh messages experience bounded queuing delays. The SMART architecture combined with AGREE protocol is significantly more scalable compared to the Intserv/RSVP model.

We introduce WRP-Lite, which is a table-driven routing protocol that uses non-optimal routes, and compare its performance with the performance of the dynamic source routing (DSR) protocol, which is an on-demand routing protocol for wireless ad-hoc networks. We evaluate the performance of WRP-Lite and DSR for varying degree of mobility and traffic in a 20-node network. The performance parameters are end-to-end delay, control overhead, percentage of packets delivered, and hop distribution. We show that WRP-Lite has much better delay and hop performance while having comparable overhead to DSR.

A novel multichannel schedule-based medium access control (MAC) protocol for ad-hoc networks, named collision-avoidance transmission scheduling (CATS) is introduced. CATS allows nodes to contend for and reserve data channels for specific time slots by means of distributed reservation and collision-avoidance handshakes. Contention is limited among nodes within two hops of one another, which provides a very efficient spatial reuse of the bandwidth available. CATS ensures that no collisions occur in successfully reserved data links, even when hidden terminals exist. Reservations in CATS support unicasting, multicasting and broadcasting at link level simultaneously and adapt to dynamic data size. The throughput achieved by CATS is analyzed for unicast traffic and broadcast traffic. Numerical results show that CATS can achieve very high throughput.

The medium-access control (MAC) protocols for wireless networks proposed or implemented to date based on collision-avoidance handshakes between the sender and receiver either require carrier sensing or the assignment of unique codes to nodes to ensure that intended receivers hear data packets without interference from hidden sources. We present and analyze a protocol that we call channel-hopping multiple access (CHMA) for multi-channel, ad-hoc networks which does not require carrier sensing or the assignment of unique codes to nodes to ensure collision-free reception of data at the intended receivers in the presence of hidden terminals. We compare CHMA against MACA-CT and show considerable improvement in the performance achieved. The correct avoidance of collisions in CHMA protocols is verified, and their throughput and delay characteristics is studied analytically. CHMA protocols are applicable to ad-hoc networks based on commercial off-the shelf spread spectrum radios operating in unlicensed frequency bands.

Media access control (MAC) protocols for wireless networks may be based on collision-avoidance handshakes between sender and receiver. Those protocols proposed or implemented to date require either carrier sensing or the assignment of unique node codes in order to ensure that intended receivers hear data packets without interference from hidden sources. We present and analyze a new collision-avoidance MAC protocol that we call receiver-initiated channel-hopping with dual polling (RICH-DP). RICH-DP is the first MAC protocol based on a receiver-initiated collision-avoidance handshake that does not require carrier sensing or the assignment of unique codes to nodes in order to ensure collision-free reception of data at the intended receivers in the presence of hidden terminals. The correct avoidance of collisions under hidden terminals is verified. The throughput and delay characteristics of RICH-DP are studied analytically, and extensive simulations are presented to verify the analysis and to present a more accurate prediction of how RICH-DP would operate in realistic scenarios. RICH-DP is applicable to ad-hoc networks based on commercial off-the-shelf frequency hopping radios operating in unlicensed frequency bands.

Single-path routing provided by today's interior gateway protocols (IGP) make extremely inefficient usage of network bandwidth, and is evident in the large end-to-end delays flows experience in single-path routing as compared to minimum-delay routing. Enhancement to OSPF such as optimized multipath have not proved adequate to bridge this large delay gap. Practical implementations of minimum-delay routing, on the other hand, have been largely unsuccessful for reasons such as scalability, slow convergence and out-of-order packet delivery. This paper proposes a traffic engineering solution that adapts the minimum-delay routing for a given traffic matrix in a way that is practical and suitable to implement in the differentiated services framework. A simple and scalable packet forwarding technique is described that offers several improvements over OSPF-OMP.

We study group loss probabilities of forward error correction (FEC) codes in shared loss multicast communication. We present a new analysis model with explicit state equations using recursive formulae. Our method looks at an FEC group as a whole, rather than analyze the number of transmissions of a particular packet. Our work applies to C(n,k) erasure codes, where any k out of n packets may decode the entire group. We find the cumulative distribution function that all leaf nodes in a shared loss tree successfully decode a C(n,k) FEC group, the probability mass function (p.m.f.) for the number of leaf nodes that successfully decode a transmission group, the expected number of packets received on successful decode and the expected number of missing packets on decode failure for a particular leaf node of the multicast tree, the p.m.f. that all leaf nodes hold the same packets in common, and the expected height of packet loss. Most of our findings generalize to arbitrary trees with non-uniform link loss. Our results also apply to non-FEC trees. We illustrate applications of our work with examples.

We introduce and analyze CARMA-MC (for collision avoidance and resolution multiple access for multiple channels), a new stable channel access protocol for multihop wireless networks with multiple channels. CARMA-MC relies on the assignment of a unique channel and a unique identifier to each node to support correct deterministic collision resolution in the presence of hidden terminals. CARMA-MC dynamically divides the channel of each node into cycles of variable length; each cycle consists of one or more receiving periods and a transmission period. During the receiving period, stations with one or more packets to send compete for the right to acquire the floor of a particular receiver's channel using a deterministic tree-splitting algorithm. Each receiving period consists of collision resolution steps. A single round of collision resolution (i.e., a success, and idle or a collision of control packets) is allowed in each contention step. The receiving period is initiated by the receiver and takes place in the channel assigned to the receiver station. The channel utilization and packet delays are studied analytically and by simulation.

Large-scale applications are characterized by a large number of dynamic and often interactive group members. The nature of these applications is such that participants are not interested in all the content transmitted. We examine three currently available techniques to scope delivery of content to interested receivers in IP multicast: filtering, where data is filtered by middleware before being passed to the application; addressing, where data is routed only to those receivers that express their interest; and hybrid approaches. We propose a framework that models large-scale application behavior. We use this framework to evaluate the performance of these applications and related protocols when the network is capable of filtering or addressing. Our results show that the current Internet architecture does not efficiently support large-scale applications because it can not efficiently manage multiple multicast groups. We show that network-level addressing is preferred to filtering and hybrid approaches given that groups are easy to create and manage. We highlight areas of research in the multicast architecture to bring about this change.

We present a practical approach to routing and anycasting with near-optimum delays taking into account the processing loads at routers and processing elements of a computer network. To accomplish this, the minimum-delay routing problem formulated by Gallager (1977) is generalized into the problem of minimum-delay routing with load-balancing to account for processing delays in network nodes (servers and routers). Gallager's theorem for necessary and sufficient conditions for minimum-delay routing is modified to include processing delays and changes of traffic levels at network nodes. The first distributed algorithm for load-balanced anycasting and routing in computer networks is presented. This algorithm, named MIDAS, provides approximate solutions to the modified necessary and sufficient conditions for minimum-delay routing. Simulations are use to compare the performance of the new algorithm with the performance of a traditional approach to sever load balancing.

Previous research has focussed on the problems associated with TCP performance in the presence of wireless links and ways to improve its performance. We present an extension to TCP Santa Cruz which improves TCP performance over lossy wireless links. TCP has no mechanism to differentiate random losses on the wireless link from congestion, and therefore treats all losses as congestive. We present a simple method in which our protocol is able to differentiate these random losses, thereby avoiding the rate-halving approach taken by standard TCP whenever any loss is detected. We compare the performance of our protocol against TCP Reno and demonstrate higher throughput and lower end-to-end delay with our approach.

The medium-access control (MAC) protocols for wireless networks proposed or implemented to date based on collision-avoidance handshakes between the sender and receiver either require carrier sensing or the assignment of unique codes to nodes to ensure that intended receivers hear data packets without interference from hidden sources (i.e. IEEE 802.11). We present and analyze a receiver-initiated channel-hopping (RICH) protocol, which is the first MAC protocol based on a receiver-initiated collision-avoidance handshake that does not require carrier sensing or the assignment of unique codes to nodes to ensure collision-free reception of data at the intended receivers in the presence of hidden terminals. The correct floor acquisition for RICH is verified, and the throughput and delay characteristics are calculated analytically. The RICH protocol presented here is applicable to ad-hoc networks based on commercial, on-the-shelf, spread spectrum frequency-hopping radios operating in unlicensed frequency bands.

We present a practical approach to internet routing that provides near-minimum delays over multiple loop-free paths to destinations. The new protocol, which we call NEAR-OPT, obtains multiple loop-free paths to destinations using long-term delay measures, and allocates destination-oriented flows over such paths using short-term delay measures to minimize delay. We compare the performance of NEAR-OPT with traditional single-path routing and the only known adaptation for dynamic networks of Gallager's minimum-delay routing algorithm. Using actual Internet traffic traces and other traffic source models, we show that NEAR-OPT provides delays comparable to the lower bounds achievable with Gallager's algorithm for static networks, provides lower delays than implementations of Gallager's algorithm in networks subject to fractal traffic, and renders far smaller delays and better use of resources than traditional single-path routing. NEAR-OPT does not depend on any global constant and is completely distributed, making it easy to implement as a loop-free distance-vector protocol similar to Cisco's EIGRP.

The core-assisted mesh protocol (CAMP) is introduced for multicast routing in ad hoc networks. CAMP generalizes the notion of core-based trees introduced for Internet multicasting into multicast meshes that have much richer connectivity than trees. A shared multicast mesh is defined for each multicast group; the main goal of using such meshes is to maintain the connectivity of multicast groups even while network routers move frequently. The CAMP consists of the maintenance of multicast meshes and loop-free packet forwarding over such meshes. Within the multicast mesh of a group, packets from any source in the group are forwarded along the reverse shortest path to the source, just as in traditional multicast protocols based on source-based trees. The CAMP guarantees that, within a finite time, every receiver of a multicast group has a reverse shortest path to each source of the multicast group. It uses cores only to limit the traffic needed for a router to join a multicast group; the failure of cores does not stop packet forwarding or the process of maintaining the multicast meshes.

We introduce a new medium access control (MAC) protocol named PDMA (poll-before-data multiple access). Most prior MAC protocols aimed at avoiding collisions of data packets in networks with hidden terminals are sender-initiated, in that the sender transmits a short request to send (RTS) asking the receiver for permission to transmit. In contrast in PDMA, when a data packet arrives at the receiver, the receiver sends a ready-to-receive-and-transmit (RT2) packet stating the identifiers of a specific sender and receiver. A node receiving an RT2 packet addressed to it as a sender is enabled to send a data packet if it has one; otherwise, if the sender specified in the RT2 is quiet, the receiver specified in the RT2 sends a clear-to-send (CTS) packet, enabling the sender of the RT2 to send its own data packet free of collisions. PDMA is shown to avoid the collision of data packets with any type of packet. An analytical model is used to show that PDMA achieves higher throughput than prior collision-avoidance protocols for wireless networks, namely MACA-BI, FAMA NCS, and MACA. Average delays in PMA are also shown to be shorter than those in CSMA.

It is shown that a unidirectional link of a network can be used for routing only if it has an inclusive cycle, which provides a path to carry routing updates from the downstream node to the upstream node joint by the unidirectional link. A new routing algorithm for networks with unidirectional links is then presented, which incrementally disseminates link-state information and selectively utilizes unidirectional links in networks. The new algorithm is verified to be correct and its complexity is analyzed. Simulations on a 20-node unidirectional network show that the new algorithm is more efficient than topology broadcasting.

We present and verify ROAM, an on-demand routing algorithm that maintains multiple loop-free paths to destinations. Each router maintains entries only for those destinations for which data flows through the router which reduces storage space requirements and the amount of bandwidth needed to maintain correct routing tables. In ROAM, routes are established and maintained on demand using diffusing computations. A router does not send updates for active destinations, unless its distance to them increases beyond a given threshold. ROAM maintains a state that informs routers when a destination is unreachable and prevents routers from sending unnecessary search packets attempting to find paths to an unreachable destination. ROAM is shown to converge in a finite time after an arbitrary sequence of topological changes and is shown to be loop-free at every instant. The time and communication complexities of ROAM are analyzed.

The Internet community has proposed the integrated services architecture (Intserv) and the signaling protocol RSVP to provide deterministic guarantees (bandwidth, delay and jitter) to individual flows. However, experience with practical systems has revealed the severe scalability problems of the Intserv model due to the amount of routing and reservation state that is required to he maintained in the routers. A natural approach to improving scalability of the Intserv architecture is through a reduction of the number of states in the routers by using aggregated flow state instead of per-flow state. We present a novel architecture that uses very few states in the routers, while still providing the deterministic guarantees of the Intserv model.

Routing algorithms in the IP Internet provide a single path between each source-destination pair and where more than one path is provided, they are paths of equal length. Single-path routing is inherently slow in responding to congestion and temporary traffic bursts; multiple paths are better suited to handle congestion. Also the paths provided in RIP and OSPF are not free of loops during times of network transition, which can be debilitating to network performance. We present a distributed routing algorithm for computing multiple paths that need not have equal length between each source-destination pair in a computer network such that they are loop-free at every instant - in steady state as well as during network transitions. The algorithm is scalable to large networks as it uses only one-hop synchronization which is unlike diffusing computations that require internodal synchronization spanning multiple hops. The safety and liveness properties of the algorithm are proven and its complexity is analyzed.

We present the source-tree adaptive routing (STAR) protocol and analyze its performance in wireless networks with broadcast radio links. Routers in STAR communicate to the neighbors their source routing trees either incrementally or in atomic updates. Source routing trees are specified by stating the link parameters of each link belonging to the paths used to reach every destination. Hence, a router disseminates link-state updates to its neighbors for only those links along paths used to reach destinations. Simulation results show that STAR is an order of magnitude more efficient than any topology-broadcast protocol, and four times more efficient than ALP, which was the most efficient table-driven routing protocol based on partial link-state information reported to date. The results also show that STAR is even more efficient than the dynamic source routing (DSR) protocol, which has been shown to be one of the best performing on-demand routing protocols.

We present a new implementation of TCP that is better suited to today's Internet than TCP Reno or Tahoe. Our implementation of TCP, which we call TCP Santa Cruz, is designed to work with path asymmetries, out-of-order packet delivery, and networks with lossy links, limited bandwidth and dynamic changes in delay. The new congestion-control and error-recovery mechanisms in TCP Santa Cruz are based on: using estimates of delay along the forward path, rather than the round-trip delay; reaching a target operating point for the number of packets in the bottleneck of the connection, without congesting the network; and making resilient use of any acknowledgments received over a window, rather than increasing the congestion window by counting the number of returned acknowledgments. We compare TCP Santa Cruz with the Reno and Vegas implementations using the ns2 simulator. The simulation experiments show that TCP Santa Cruz achieves significantly higher throughput, smaller, delays, and smaller delay variances than Reno and Vegas. TCP Santa Cruz is also shown to prevent the swings in the size of the congestion window that typify TCP Reno and Tahoe traffic, and to determine the direction of congestion in the network and isolate the forward throughput from events on the reverse path.

The Core Assisted Mesh Protocol (CAMP) is introduced for multicast routing in ad hoc networks. CAMP generalizes the notion of core-based trees introduced for internet multicasting into multicast meshes that have much richer connectivity than trees. A shared multicast mesh is defined for each multicast group; the main goal of using such meshes is to maintain the connectivity of multicast groups even while network routers move frequently. CAMP consists of the maintenance of multicast meshes and loop-free packet forwarding over such meshes. Within the multicast mesh of a group, packets from any source in the group are forwarded along the reverse shortest path to the source, just as in traditional multicast protocols based on source-based trees. CAMP guarantees that, within a finite time, every receiver of a multicast group has a reverse shortest path to each source of the multicast group. Multicast packets for a group are forwarded along the shortest paths from sources to receivers defined within the group's mesh. CAMP uses cores only to limit the traffic needed for a router to join a multicast group; the failure of cores does not stop packet forwarding or the process of maintaining the multicast meshes.

A new multichannel MAC protocol called hop-reservation multiple access (HRMA) for wireless ad-hoc networks (multi-hop packet radio networks) is introduced, specified and analyzed. HRMA is based on simple half-duplex, very slow frequency-hopping spread spectrum (FHSS) radios and takes advantage of the time synchronization necessary for frequency-hopping. HRMA allows a pair of communicating nodes to reserve a frequency hop using a reservation and handshake mechanism that guarantee collision-free data transmission in the presence of hidden terminals. We analyze the throughput achieved in HRMA for the case of a hypercube network topology assuming variable-length packets, and compare it against the multichannel slotted ALOHA protocol, which represents the current practice of MAC protocols in commercial ad-hoc networks based on spread spectrum radios, such as Metricom's Ricochet system. The numerical results show that HRMA can achieve much higher throughput than multichannel slotted ALOHA within the traffic-load ranges of interest, especially when the average packet length is large compared to the duration of a dwell time in the frequency hopping sequence, in which case the maximum throughput of HRMA is close to the maximum possible value.

Many medium-access control (MAC) protocols for wireless networks proposed or implemented to date are based on collisionavoidance handshakes between sender and receiver. In the vast majority of these protocols, including the IEEE 802.11 standard, the handshake is sender initiated, in that the sender asks the receiver for permission to transmit using a short control packet, and transmits only after the receiver sends a short clear-to-send notification. We analyze the effect of reversing the collision-avoidance handshake, making it receiver initiated and compare the performance of a number of these receiver-initiated protocols with the performance of protocols based on sender-initiated collision avoidance. The receiver-initiated protocols we present make use of carrier sensing, and are therefore applicable to either baseband or slow frequencyhopping radios in which an entire packet can be sent within the same frequency hop (which is the case of FHSS commercial radios that support IEEE 802.11). It is shown that the best-performing MAC protocol based on receiver-initiated or sender-initiated collision avoidance is one in which a node with data to send transmits a dual-purpose small control packet inviting a given neighbor to transmit and asking the same neighbor for permission to transmit.

We present Keyed HIP (KHIP), a secure, hierarchical multicast routing protocol. We show that other shared-tree multicast routing protocols are subject to attacks against the multicast routing infrastructure that can isolate receivers or domains or introduce loops into the structure of the multicast routing tree. KHIP changes the multicast routing model so that only trusted members are able to join the multicast tree. This protects the multicast routing against attacks that could form branches to unauthorized receivers, prevents replay attacks and limits the effects of flooding attacks. Untrusted routers that are present on the path between trusted routers cannot change the routing and can mount no denial-of-service attack stronger than simply dropping control messages. KHIP also provides a simple mechanism for distributing data encryption keys while adding little overhead to the protocol.

The conventional approach to routing in computer networks consists of using a heuristic to compute a single shortest path from a source to a destination. Single-path routing is very responsive to topological and link-cost changes; however, except under light traffic loads, the delays obtained with this type of routing are far from optimal. Furthermore, if link costs are associated with delays, single-path routing exhibits oscillatory behavior and becomes unstable as traffic loads increase. On the other hand, minimum-delay routing approaches can minimize delays only when traffic is stationary or very slowly changing.We present a "near-optimal" routing framework that offers delays comparable to those of optimal routing and that is as flexible and responsive as single-path routing protocols proposed to date. First, an approximation to the Gallager's minimum-delay routing problem is derived, and then algorithms that implement the approximation scheme are presented and verified. We introduce the first routing algorithm based on link-state information that provides multiple paths of unequal cost to each destination that are loop-free at every instant. We show through simulations that the delays obtained in our framework are comparable to those obtained using the Gallager's minimum-delay routing. Also, we show that our framework renders far smaller delays and makes better use of resources than traditional single-path routing.

We present the source-tree adaptive routing (STAR) protocol, which we show through simulation experiments to be far more efficient than the dynamic source routing (DSR) protocol, which has been shown to be one of the best performing on-demand routing protocols. A router in STAR communicates to its neighbors the parameters of its source routing tree, which consists of each link that the router needs to reach every destination. To conserve transmission bandwidth and energy, a router transmits changes to its source routing tree only when the router detects new destinations, the possibility of looping, or the possibility of node failures or network partitions.

We present the transport unaware link improvement protocol (TULIP), which dramatically improves the performance of TCP over lossy wireless links, without competing with or modifying the transport- or network-layer protocols. TULIP is tailored for the half-duplex radio links available with today's commercial radios and provides a MAC acceleration feature applicable to collision-avoidance MAC protocols (e.g., IEEE 802.11) to improve throughput. TULIP's timers rely on a maximum propagation delay over the link, rather than performing a round-trip time estimate of the channel delay. The protocol does not require a base station and keeps no TCP state. TULIP is exceptionally robust when bit error rates are high; it maintains high goodput, i.e., only those packets which are in fact dropped on the wireless link are retransmitted and then only when necessary. The performance of TULIP is compared against the performance of the Snoop protocol (a TCP-aware approach) and TCP without link-level retransmission support. The results of simulation experiments using the actual code of the Snoop protocol show that TULIP achieves higher throughput, lower packet delay, and smaller delay variance.

A new channel access protocol for ad-hoc networks based on topology-dependent transmission scheduling, named collision-avoidance time allocation (CATA), is introduced. CATA allows nodes to contend for and reserve time slots by means of a distributed reservation and handshake mechanism. Contention is limited among nodes within two hops of one another, which provides a very efficient spatial reuse of the bandwidth available. CATA ensures that no collisions occur in successfully reserved time slots, even when hidden terminals exist. Reservations in CATA support unicasting, multicasting and broadcasting simultaneously, and adapt to dynamic service time. The throughput achieved by CATA is analyzed for the case of a fully-connected network topology. Numerical results show that CATA can achieve very high throughput.

The core-assisted mesh protocol (CAMP) is introduced for multicast routing in ad hoc networks. CAMP generalizes the notion of core-based trees introduced for internet multicasting into multicast meshes that have much richer connectivity than trees. A shared multicast mesh is defined for each multicast group; the main goal of using such meshes is to maintain the connectivity of multicast groups even while network routers move frequently, CAMP consists of the maintenance of multicast meshes and loop-free packet forwarding over such meshes. Within the multicast mesh of a group, packets from any source in the group are forwarded along the reverse shortest path to the source, just as in traditional multicast protocols based on source-based trees. CAMP guarantees that within a finite time, every receiver of a multicast group has a reverse shortest path to each source of the multicast group. Multicast packets for a group are forwarded along the shortest paths front sources to receivers defined within the group's mesh. CAMP uses cores only to limit the traffic needed for a router to join a multicast group; the failure of cores does not stop packet forwarding or the process of maintaining the multicast meshes.

The Group Allocation Multihop Multiple Access (GAMMA) protocol is presented; this protocol schedules data traffic over a multihop, multi-channel, wireless network. GAMMA provides excellent performance and remains stable under all network load levels by dividing the channel into cycles; each cycle is composed of a combination of contention and data slots. Every station in the network has a unique channel for receiving data. Each station maintains a set of stations called the "transmission group", only members of this group are allowed to transmit data collision-free to the station maintaining the group.

We propose and analyze a specific set of access rules, or "spectrum etiquette", for the 59-64 GHz unlicensed band to allow systems from different manufacturers with different physical and medium-access control protocols to co-exist, sharing the large available bandwidth without interference. The proposed etiquette is unique in that heterogeneous systems are able to co-exist with one another without monitoring the entire band by means of transmissions over a common, narrow band control channel used to establish collision-free transmission schedules over the channels allocated for data transmission within the 59-64 GHz band. Because no common physical layer can be assumed among different systems, the control channel is needed for the systems to schedule transmissions in the rest of the band, and the only means by which systems can communicate with one another over the control channel is the duration of each others' transmissions, which are perceived only as noise. A transmission encoding is defined based on this basic feedback to allow systems to ascertain which system can use which data channel at which time without interference. Analytical and simulation results are presented showing that the proposed etiquette is fair to all the co-existing systems, fully utilizes the spectrum, provides bounded delays for data-channel acquisition time by any given system, and provides minimum channel-use guarantees.

A new multichannel MAC protocol called hop reservation multiple access (HRMA) for packet-radio networks is introduced, specified and analyzed. HRMA is based on very-slow frequency-hopping spread spectrum (FHSS) and takes advantage of the time slotting necessary for frequency hopping. HRMA allows a pair of communicating nodes to reserve a frequency hop (channel) using a hop reservation and handshake mechanism on every hop to guarantee collision-free data transmission in the presence of hidden terminals. HRMA provides a baseline to offer QoS in ad-hoc networks based on simple half-duplex slow FHSS radios. We analyze the throughput achieved in HRMA for the case of a fully-connected network assuming variable-length packets, and compare it against an ideal multichannel access protocol and the multichannel slotted ALOHA protocol. The numerical results show that HRMA can achieve much higher throughput than multichannel slotted ALOHA in the traffic-load ranges of interest especially when the average packet length is large compared to a slot size, in which case the maximum throughput of HRMA is close to what can be obtained with an ideal protocol.

We present and verify the adaptive link-state protocol (ALP), a new link-state routing protocol that does not require the state of each link to be flooded to the entire internetwork, or to entire areas if hierarchical routing is used. A router in ALP disseminates link-state updates incrementally to its neighbors for only those links along paths used to reach destinations. Link-state updates are validated using time stamps and contain the same information used in other link-state protocols. For the case of neighbor routers connected through a broadcast medium, a designated router is distributedly elected for each link state reported over the medium, rather than requiring a designated router to report every topology change over the broadcast medium, like OSPF does. Simulation experiments illustrate that ALP is as efficient as the distributed-Bellman Ford algorithm when distances to destinations do not increase and resources do not fail, and more efficient than traditional link-state protocols based on flooding after distances increase or resources fail. ALP also outperforms the link-vector algorithm (LVA), which is the only prior routing algorithm based on selective dissemination of link states.

An area-based link-vector algorithm (ALVA) is introduced for the distributed maintenance of routing information in very large internetworks. According to ALVA, destinations in an internetwork are aggregated in areas in multiple levels of hierarchy. Routers maintain a database that contains a subset of the topology at each level of the hierarchy. This subset corresponds to those links used in preferred paths to reach destinations (nodes inside the same immediate area or remote areas). The ALVA is the first hierarchical routing algorithm based on link-state information that does not require complete topology information at each level in the hierarchy. The correctness of the ALVA is verified. Simulation results are presented showing that the ALVA outperforms the OSPF in terms of communication and storage overhead.

We introduce a new stable multiple access protocol for broadcast channels shared by multiple stations, which we call the incremental collision resolution multiple access (ICRMA) protocol. ICRMA dynamically divides the channel into cycles of variable length; each cycle consists of a contention period and a queue-transmission period. The queue-transmission period is a variable-length train of packets, which are transmitted by stations that have been added to the distributed transmission queue by successfully completing a collision-resolution round in a previous contention period. During the contention period, stations with one or more packets to send compete for the right to be added to the data-transmission queue using a deterministic tree-splitting algorithm. A single round of collision resolution is allowed in each contention period. Analytical results show that collision resolution in ICRMA is much more efficient than DQRAP's. Simulation and analytical results show that ICRMA's throughput is within 5% of the throughput achieved by the ideal channel access protocol based on a distributed transmission queue and incremental collision resolution.

A new distributed algorithm for the dynamic computation of multiple loop-free paths from source to destination in a computer network or Internet are presented, validated, and analyzed. According to this algorithm, which is called DASM (diffusing algorithm for shortest multipath), each router maintains a set of entries for each destination in its routing table, and each such entry consists of a set of tuples specifying the next router and distance in a loop-free path to the destination. DASM guarantees instantaneous loop freedom of multipath routing tables by means of a generalization of Dijkstra and Scholten's diffusing computations. With generalized diffusing computations, a node in a directed acyclic graph (DAG) defined for a given destination has multiple next nodes in the DAG and is able to modify the DAG without creating a directed loop. DASM is shown to be loop-free at every instant, and its average performance is analyzed by simulation and compared against an ideal link-state algorithm and the diffusing update algorithm (DUAL).

The performance of the FAMA-NCS protocol in ad-hoc networks is analyzed. FAMA-NCS (for floor acquisition multiple access with nonpersistent carrier sensing) guarantees that a single sender is able to send data packets free of collisions to a given receiver at any given time. FAMA-NCS is based on a three-way handshake between sender and receiver in which the sender uses non-persistent carrier sensing to transmit a request-to-send (RTS) and the receiver sends a clear-to-send (CTS) that lasts much longer than the RTS to serve as a "busy tone" that forces all hidden nodes to back off long enough to allow a collision-free data packet to arrive at the receiver. It is shown that that FAMA-NCS performs better than ALOHA, CSMA, and all prior proposals based on collision avoidance dialogues (e.g., MACA, MACAW, and IEEE 802.11 DFWMAC) in the presence of hidden terminals. Simulations experiments are used to confirm the analytical results. I. INTRODUCTION The medium access control (MAC) protocol wi...

3-14

This paper presents a new, exible approach to inter-domain multicast routing. The HIP protocol introduces the idea of \\virtual routers" as a method of organizing the control of an entire domain so as to appear as a single router on a higher-level shared tree. HIP then routes between domains using the Ordered Core Based Tree (OCBT) protocol, and allows recursive application of virtual routers to create a multi-leveled hierarchy while providing ecient methods of distributing the location of the center point for the tree. The advantages of this approach include improved robustness, the ability to route between heterogeneous domains, and a signicant reduction in the amount of bandwidth consumed in control trac and in the amount of state stored at each router over existing hierarchical multicast protocols. 1 Introduction There are two compelling reasons for developing hierarchical multicast routing protocols. The rst is to provide a means of routing between heterogeneous domains that m...

Group collaboration in distributed multimedia environments extends gradually to larger groups and wide area networks. While reliable multicasting has made significant advancements in recent years, effective mechanisms to synchronize and coordinate work within large multicast groups and across long distances are still lacking. Group coordination is here understood as the mediated access to shared remote resources in synchronous groupwork, as for example in telecollaboration and distributed simulation environments, complementing protocols for group membership, media synchronization and reliable ordered multicast. A comparative analytic model for known classes of group coordination mechanisms, ranging from socially mediated control to floor control in ring and tree topologies, is presented. It is shown that hierarchical group coordination is the most efficient and scalable approach to date. Based on these findings, a novel protocol is described, which dynamically organizes participants in a multilevel control tree and aggregates resource sharing directives on the paths between interacting stations.

The bounded shortest multicast algorithm (BSMA) is presented for constructing minimum-cost multicast trees with delay constraints. The BSMA can handle asymmetric link characteristics and variable delay bounds on destinations, specified as real values, and minimizes the total cost of a multicast routing tree. Instead of the single-pass tree construction approach used in most previous heuristics, the new algorithm is based on a feasible-search optimization strategy that starts with the minimum-delay multicast tree and monotonically decreases the cost by iterative improvement of the delay-bounded multicast tree. The BSMA's expected time complexity is analyzed, and simulation results are provided showing that BSMA can achieve near-optimal cost reduction with fast execution.

We specify and analyze two variants of floor acquisition multiple access protocols for CSMA single-channel wireless LANs (WLANs) with hidden terminals. One variant assumes that all stations have the same functionality, and the other assumes base station control. These are the first protocols that solve the hidden-terminal problems of single-channel WLANS. Stations use carrier sensing and a three way handshake, just as advocated in MACA, IEEE 802.11 and FAMA-NTR introduced in the past. However, the clear to send (CTS) from a receiver lasts long enough to be able to jam any hidden sender that did not hear the request to send (RTS) being acknowledged and who started sending its RTS after the receiver started sending the CTS. We verify that this jamming of the "offending senders" by the receivers permits floor acquisition to be enforced correctly, i.e., that no data packet sent by a sender will ever collide at the intended receiver with any packet sent by any other station hidden or exposed from the sender. The performance of these protocols is compared by simulation with the performance of MACAW reported in the past.

Collision avoidance and resolution multiple access (CARMA) protocols establish a three-way handshake between sender and receiver to attempt to avoid collisions, and resolve those collisions that occur. This paper describes and analyzes CARMA protocols that resolve collisions up to the first success obtained by running a tree-splitting algorithm for collision resolution. An upper bound is derived for the average costs of resolving collisions of floor requests using the tree-splitting algorithm is obtained and applied to the computation of the average channel utilization in a fully connected network with a large number of stations. Our analysis indicates that, because CARMA protocols guarantee a successful transmission for every busy period of the channel, it achieves higher throughput than other contention-based MAC protocols based on collision-avoidance handshakes.

To reduce or eliminate the implosion of acknowledgments at the source of a very large multicast group, current reliable multicast protocols either organize the receivers of a group into a tree or ring, or implement negative acknowledgment (NAK) avoidance algorithms based on random timers. All of these approaches have their limitations and advantages. We present a ring-based reliable multicast protocol, called the evenly-loaded ring protocol (ELRP) which removes processing bursts from nodes in the ring. ELRP achieves throughputs as good as those obtained with tree-based protocols and better than those of receiver-initiated protocols with NAK avoidance. We propose a deterministic NAK avoidance (DNKA) algorithm based on ELRP that performs better than the random NAK avoidance scheme (RNKA). Because tree structures are better suited than rings for wide areas involving paths with long delays, we propose the hybrid reliable multicast protocol (HRMP) which organizes receivers into a backbone acknowledgement tree that connects local areas. Any tree-based protocol with positive acknowledgement can be run in the backbone acknowledgement tree, and ELRP is run in the local areas. The maximum achievable throughput in HRMP is analyzed, which shows that it is completely scalable. The delay of DNKA and RNKA schemes are also analyzed which shows that compared with RNKA, DNKA reduces the retransmission delay significantly.

Routing protocols based on the distribution of link-state information rely on sequence numbers to validate information that a router receives. A fundamental problem is to bound the sequence-number space. We propose a new sequence-number reset algorithm that needs neither periodic retransmissions nor age fields. It is based on a recursive query-response procedure and is designed to handle resource failures during operation. This new algorithm is applicable to routing protocols based on both flooding and selective distribution of link-state information. The correctness of the algorithm is verified in the context of selective dissemination of topology information, and its complexity analyzed. Because the reset algorithm does not use any aging, the distribution of new link-state information or the purging of old information is always done in a time proportional to the time it takes to traverse the network.

The IP-multicast architecture is extended with addressing information along multicast routing trees that permits more efficient and sophisticated multicast routing options and encourages communication and cooperation between IP and higher-layer protocols. The Addressable Internet Multicast (AIM) architecture is introduced that enables sources to restrict the delivery of packets to a subset of the receivers in a multicast group on a per-pocket basis, permits receivers to listen to subsets of sources on a subscription basis, provides nearest-host routing, and allows higher-layer protocols to place packets into application-defined logical streams, so that hosts may direct the multicast routing of packets based on application-defined contexts. In addition, the Reliable Multicast Architecture (RMA) is introduced to support end-to-end reliable multicasting using heterogeneous reliable multicast protocols and providing acknowledgment trees implicitly, thereby eliminating the ACK implosion problem and allowing NAK-avoidance algorithms to work within local groups.

The CARMA-NTG protocol is presented and analyzed. CARMA-NTG dynamically divides the channel into cycles of variable length; each cycle consists of a contention period and a group-transmission period. During the contention period, a station with one or more packets to send competes for the right to be added to the group of stations allowed to transmit data without collisions; this is done using a collision resolution splitting algorithm based on a request-to-send/clear-to-send (RTS/CTS) message exchange with non-persistent carrier sensing. CARMA-NTG ensures that one station is added to the group transmission period if one or more stations send requests to be added in the previous contention period. The group-transmission period is a variable-length train of packets, which are transmitted by stations that have been added to the group by successfully completing an RTS/CTS message exchange in previous contention periods. As long as a station maintains its position in the group, it is able to transmit data packets without collision, An upper bound is derived for the average costs of obtaining the first success in the splitting algorithm. This bound is then applied to the computation of the average channel utilization in a fully connected network with a large number of stations. These results indicate that collision resolution is a powerful mechanism in combination with floor acquisition and group allocation multiple access.

The group allocation multiple access with collision detection (GAMA/CD) protocol for scheduling variable-length packet transmissions in a local area network is specified and analyzed. The GAMA/CD provides the advantages of both TDMA and CSMA/CD by maintaining a dynamically-sized cycle that varies in length depending on the network load; each cycle is composed of a contention period and a group-transmission period. During the contention period, a station with one or more packets to send competes for membership in the transmission group. Once a member of the transmission group, a station is able to send data without collision during each cycle; as long as a station has data to send, it maintains its position in the group. This can be viewed as either allowing stations to "share the floor" in an organized manner, or as establishing frames that are not synchronized on a slot-basis and vary their length dynamically based on demand. Both the throughput and the delay of GAMA/CD are presented and analyzed. To validate our analysis, the results of both models are compared to the throughput and delay produced by a simulation of GAMA/CD.

We present a new hierarchical routing algorithm that combines the loop-free path-finding algorithm (LPA) with the area-based hierarchical routing scheme first proposed by McQuillan (1974) for distance-vector algorithms. The new algorithm, which we call the hierarchical information path-based routing (HIPR) agorithm, accommodates an arbitrary number of aggregation levels and can be viewed as a distributed version of Dijkstra's algorithm running over a hierarchical graph. The HIPR is verified to be loop-free and correct. Simulations are used to show that the HIPR is much more efficient than the OSPF in terms of speed, communication and processing overhead required to converge to correct routing tables. The 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.

This paper presents a new protocol, the ordered core based tree (OCBT) protocol, which remedies several shortcomings of the core based tree (CBT) multicast protocol. We show that the CBT protocol can form loops during periods of routing instability, and that it can consistently fail to build a connected multicast tree, even when the underlying routing is stable. The OCBT protocol provably eliminates these deficiencies and reduces the latency of tree repair following a link or core failure. The OCBT also improves scalability by allowing flexible placement of the cores that serve as points of connection to a multicast tree. Simulation results show that the amount of control traffic in OCBT is comparable to that in CBT.

We analyze the security requirements of distance-vector routing protocols, identify their vulnerabilities, and propose countermeasures to these vulnerabilities. The innovation we propose involves the use of mechanisms from the path-finding class of distance-vector protocols as a solution to the security problems of distance-vector protocols. The result is a proposal that effectively and efficiently secures distance-vector protocols in constant space.

The floor acquisition multiple access (FAMA) discipline is analyzed in networks with hidden terminals. According to FAMA, control of the channel (the floor) is assigned to at most one station in the network at any given time, and this station is guaranteed to be able to transmit one or more data packets to different destinations with no collisions. The FAMA protocols described consist of non-persistent carrier or packet sensing, plus a collision-avoidance dialogue between a source and the intended receiver of a packet. Sufficient conditions under which these protocols provide correct floor acquisition are presented and verified for networks with hidden terminals; it is shown that FAMA protocols must use carrier sensing to support correct floor acquisition. The throughput of FAMA protocols is analyzed for single-channel networks with hidden terminals; it is shown that carrier-sensing FAMA protocols perform better than ALOHA and CSMA protocols in the presence of hidden terminals.

In network multimedia applications such as multiparty teleconferencing, users often need to send the same information to several (but not necessarily all) other users. To manage such one-to-many or many-to-many communication efficiently in wide-area internetworks, it is imperative to support and perform multicast routing. Multicast routing sends a single copy of a message from a source to multiple receivers over a communication link that is shared by the paths to the receivers. Loop-freedom is an especially important consideration in multicasting because applications using multicasting tend to be multimedia and bandwidth intensive, and loops in multicast routing duplicate looping packets. We present and verify a new multicast routing protocol, called multicast Internet protocol (MIP), which offers a simple and flexible approach to constructing both group-shared and shortest-paths multicast trees. MIP can be sender-initiated or receiver-initiated or both; therefore, it can be tailored to the particular nature of an application's group dynamics and size. MIP is independent of the underlying unicast routing algorithms used. MIP is robust and adapts under dynamic network conditions (topology or link cost changes) to maintain loop-free multicast routing. Under stable network conditions, MIP has no maintenance or control message overhead. We prove that MIP is loop-free at every instant, and that it is deadlock-free and obtains multicast routing trees within a finite time after the occurrence of an arbitrary sequence of topology or unicast changes.

A loop-free path-finding algorithm (LPA) is presented; this is the first routing algorithm that eliminates the formation of temporary routing loops without the need for internodal synchronization spanning multiple hops of the specification of complete or variable-size path information. Like other previous algorithms, the LPA operates by specifying the second-to-last hop and distance to each destination; this feature is used to ensure termination. In addition, the LPA uses an interneighbor synchronization mechanism to eliminate temporary routing loops. A detailed proof of the LPAs correctness and loop-freedom property is presented and its complexity is evaluated. The LPAs average performance is compared by simulation with the performance of algorithms representative of the state of the art in distributed routing, namely an ideal link-state (ILS) algorithm, a loop-free algorithm that is based on internodal coordination spanning multiple hops (DUAL) and a path-finding algorithm without the interneighbor synchronization mechanism. The simulation results show that the LPA is a more scalable alternative than DUAL and ILS in terms of the average number of steps, messages, and operations needed for each algorithm to converge after a topology change.

We analyze the maximum throughput that the known classes of reliable multicast protocols can attain. A new taxonomy of reliable multicast protocols is introduced based on the premise that the mechanisms used to release data at the source after correct delivery should be decoupled from the mechanisms used to pace the transmission of data and to effect error recovery. Receiver-initiated protocols, which are based entirely on negative acknowledgments (NAKs) sent from the receivers to the sender, have been proposed to avoid the implosion of acknowledgments (ACKs) to the source. However, these protocols are shown to require infinite buffers in order to prevent deadlocks. Two other solutions to the ACK-implosion problem are tree-based protocols and ring-based protocols. The first organize the receivers in a tree and send ACKs along the tree; the latter send ACKs to the sender along a ring of receivers. These two classes of protocols are shown to operate correctly with finite buffers. Following our taxonomy, the maximum attainable throughput by the known classes of reliable multicast protocols is analyzed. It is shown that tree-based protocol constitute the most scalable class of all reliable multicast protocols proposed to date.

Two protocols for scheduling variable-length packet transmissions in an optical passive star network using wavelength division multiplexing (WDM) are specified and analyzed. These protocols require: a separate channel for transmission of control packets, a fixed transmitter and receiver and a tunable transmitter and receiver. The distinction between these protocols and other WDM protocols is that message transmissions are initiated by the receipt of a control message; other schemes schedule packet transmission for some fixed point in the future. This flexibility allows these protocols to avoid "head-of-line" blocking which is a problem encountered in some other protocols. The protocols presented place no constraints on the size of a message, the size of a packet or on the number of available data channels; maintain a distributed queue for each of the output nodes; and guarantee that there are no receiver or data channel collisions. The delay characteristics of these protocols are analyzed and compared to those of the TTAS algorithm.

We present a framework for the modeling of multipath routing in connectionless networks that dynamically adapt to network congestion. The basic routing protocol uses a short-term metric based on hop-by-hop credits to reduce congestion over a given link, and a long-term metric based on end-to-end path delay to reduce delays from a source to a given destination. A worst-case bound on the end-to-end path delay is derived under three architectural assumptions: each router adopts weighted fair queueing (or packetized generalized processor sharing) service discipline on a per destination basis, a permit-bucket filter is used at each router to regulate traffic flow on a per destination basis, and all paths are loop free. The shortest multipath routing protocol regulates the parameters of the destination-oriented permit buckets and guarantees that all portions of a multipath are loop free.

Such interactive, distributed multimedia applications as shared whiteboards, group editors, and simulations require reliable concurrent multicast services, i.e., the reliable dissemination of information from multiple sources to all the members of a group. Furthermore, it makes sense to offer that service on top of the increasingly available IP multicast service, which offers unreliable multicasting. This paper establishes that concurrent reliable multicasting over the Internet should be based on reliable multicast protocols based on a shared acknowledgment tree. First, we show that organizing the receivers of a reliable multicast group into an acknowledgment tree and using NAK-avoidance with periodic polling in local groups inside such a tree provides the highest maximum throughput among all classes of reliable multicast protocols proposed to date. Second, we introduce Lorax, which demonstrates the viability of implementing a reliable multicasting approach in the Internet based on acknowledgment trees in a scalable manner. Lorax is the first known protocol that constructs and maintains a single acknowledgment tree for reliable concurrent multicasting, eliminates the need to maintain an acknowledgment tree for each source of a reliable multicast group, and can be used in combination with any of several tree-based reliable multicast protocols proposed to date.

Collision avoidance and resolution multiple access (CARMA) protocols are presented and analyzed.These protocols use a floor acquisition multiple access strategy based on carrier sensing, together with collision resolution of floor requests (RTS) based on a treesplitting algorithm.For analytical purposes, an upper bound is derived for the average costs of resolving collisions of floor requests using the tree-splitting algorithm.This bound is then applied to the computation of the average channel utilization in a fully connected network with a large number of stations.Under light-load conditions, CARMA protocols achieve the same average throughput as floor acquisition multiple access (FAMA) protocols.It is also shown that, as the arrival rate of RTSs increases, the throughput achieved by CARMA protocols is close to the maximum throughput that any FAMA protocol can achieve if propagation delays and the control packets used to acquire the floor are much smaller than the data packet trains sent by stations.Simulation results validate the simplifying approximations made in the analytical model.Our analysis results indicate that collision resolution makes floor acquisition multiple access much more effective.

In distributed network applications such as multiparty teleconferencing, users often need to send the same message to several other users. To achieve such one-to-many or many-to-many communication efficiently in wide-area internetworks, it is imperative to support multicasting, i.e., concurrent sending of messages from one source to multiple receivers. The current IP architecture for multicast routing, the core-based tree (CBT) protocol, and protocol independent multicast (PIM) protocol save a number of limitations for very large internets. To eliminate their limitations, we propose a new multicast routing protocol, called scalable Internet multicast protocol (SIMP).

A new heuristic algorithm is presented for constructing minimum-cost multicast trees with delay constraints. The new algorithm can set variable delay bounds on destinations and handles two variants of the network cost optimization goal: one minimizing the total cost (total bandwidth utilization) of the tree, and another minimizing the maximal link cost (the most congested link). Instead of the single-pass tree construction approach used in most previous heuristics, the new algorithm is based on a feasible search optimization method which starts with the minimum-delay tree and monotonically decreases the cost by iterative improvement of the delay-bounded tree. The optimality of the costs of the delay-bounded trees obtained with the new algorithm is analyzed by simulation. Depending on how tight the delay bounds are, the costs of the multicast trees obtained with the new algorithm are shown to be very close to the costs of the trees obtained by the Kou, Markowsky and Berman's algorithm (1981).

Article FAMA-PJ: a channel access protocol for wireless LANs Share on Authors: Chane L. Fullmer Computer Engineering, University of California, Santa Cruz, California Computer Engineering, University of California, Santa Cruz, CaliforniaView Profile , J. J. Garcia-Luna-Aceves Computer Engineering, University of California, Santa Cruz, California Computer Engineering, University of California, Santa Cruz, CaliforniaView Profile Authors Info & Claims MobiCom '95: Proceedings of the 1st annual international conference on Mobile computing and networkingDecember 1995 Pages 76–85https://doi.org/10.1145/215530.215559Online:01 December 1995Publication History 38citation447DownloadsMetricsTotal Citations38Total Downloads447Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The authors present a new distance-vector routing protocol for a packet radio network. The new distributed routing protocol, Wireless Routing Protocol (WRP), works on the notion of second-to-last hop node to a destination. WRP reduces the number of cases in which a temporary routing loop can occur and also provides a mechanism for the reliable transmission of update messages. The performance of WRP has been compared quantitatively by simulations with that of distributed Bellman-Ford (DBF), DUAL (a loop-free, distance-vector algorithm), and an ideal link-state algorithm (ILS) that represents the state of the art of Internet routing in a highly dynamic environment. The simulation results indicate that WRP is the most efficient of the algorithms simulated in a wireless environment.

A family of medium access control protocols for single-channel packet radio networks is specified and analyzed. These protocols are based on a new channel access discipline called floor acquisition multiple access (FAMA), which consists of both carrier sensing and a collision-avoidance dialogue between a source and the intended receiver of a packet. Control of the channel (the floor) is assigned to at most one station in the network at any given time, and this station is guaranteed to be able to transmit one or more data packets to different destinations with no collision with transmissions from other stations. The minimum length needed in control packets to acquire the floor is specified as a function of the channel propagation time. The medium access collision avoidance (MACA) protocol proposed by Karn and variants of CSMA based on collision avoidance are shown to be variants of FAMA protocols when control packets last long enough compared to the channel propagation delay. The throughput of FAMA protocols is analyzed and compared with the throughput of non-persistent CSMA. This analysis shows that using carrier sensing as an integral part of the floor acquisition strategy provides the benefits of MACA in the presence of hidden terminals, and can provide a throughput comparable to, or better than, that of non-persistent CSMA when no hidden terminals exist.

We have present a new method for distributed routing in computer networks and internets using link-state information. Link vector algorithms (LVA) are introduced for the distributed maintenance of routing information in large networks and internets.

The diffusing update algorithms (DUAL) constitute a family of distributed routing algorithms that has been shown to be loop-free at every instant, to converge after an arbitrary sequence of link-cost or topological changes, and to outperform all other loop-free routing algorithms previously proposed from the standpoint of the combined temporal, message, and storage complexities. Two hierarchical routing schemes based on DUAL are presented to make it more applicable to very large internets. A scheme based on McQuillan's (1974, 1980) hierarchical routing scheme and a backbone-oriented scheme, similar to the one used in OSPF, are introduced to reduce the amount of routing information maintained at each router. The performance of these schemes is compared by simulation to the performance of the basic DUAL, an ideal routing algorithm based on topology broadcast, and OSPF. The simulation results suggest that DUAL with areas outperforms OSPF, and provide additional insight on the performance of OSPF, EIGRP, and area-based routing algorithms in general.>

A new family of routing algorithms for the distributed maintenance of routing information in large networks and internets is introduced. This family is called link vector algorithms (LVA), and is based on the selective diffusion of link-state information based on the distributed computation of preferred paths, rather than on the flooding of complete link-state information based on the distributed computation of preferred paths, rather than on the flooding of complete link-state information to all routers. According to LVA, each router maintains a subset of the topology that corresponds to the links used by its neighbor routers in their preferred paths to known destinations. Based on that subset of topology information, the router derives its own preferred paths and communicates the corresponding link-state information to its neighbors. An update message contains a vector of updates; each such update specifies a link and its parameters. LVAs can be used for different types of routing. The correctness of LVA is verified for arbitrary types of routing when correct and deterministic algorithms are used to select preferred paths at each router. LVA is shown to have smaller complexity than link-state and distance-vector algorithms, and to have better average performance than the ideal topology-broadcast algorithm and the distributed Bellman-Ford algorithm.

A family of distributed algorithms for the dynamic computation of the shortest paths in a computer network or internet is presented, validated, and analyzed. According to these algorithms, each node maintains a vector with its distance to every other node. Update messages from a node are sent only to its neighbors; each such message contains a distance vector of one or more entries, and each entry specifies the length of the selected path to a network destination, as well as an indication of whether the entry constitutes an update, a query, or a reply to a previous query. The new algorithms treat the problem of distributed shortest-path routing as one of diffusing computations, which was first proposed by Dijkstra and Scholten (1980). They improve on a number of algorithms introduced previously. The new algorithms are shown to converge in finite time after an arbitrary sequence of link cost or topological changes, to be loop-free at every instant, and to outperform all other loop-free routing algorithms previously proposed from the standpoint of the combined temporal, message, and storage complexities.>

The author presents, verifies, and analyzes a new routing algorithm called the labeled distance-vector routing algorithm (LDR), that is loop-free at every instant, eliminates the counting-to-infinity problem of the distributed Bellman-Ford (DBF) algorithm, operates with arbitrary link and node delays, and provides shortest paths a finite time after the occurrence of an arbitrary sequence of topological changes. In contrast to previous successful approaches to loop-free routing, LDR maintains DBF's row-independence property and does not require internodal coordination spanning multiple loops. The new algorithm is shown to be loop-free and to converge in a finite time after an arbitrary sequence of topological changes. Its performance is compared with the performance of other distributed routing algorithms.>

The dynamics of shortest-path routing algorithms bss.ed on distance vectors and link states are investigated.Detailed quantitative comparisons of the distributed Belhnen-Ford algorithm used in several routing protocols in the paa~an ideal link-state ttlgonthm similar to the one used in OSPF and in the 0S1 intradomain routing protocol, and a loop-free distance-vector algorithm, are made for the network topologies of the 1988 ARPANET, LOS-NE'ITOS, DOE-ESNET, and the NSFNET T1 Backbone.Comparisons include the response of the algorithms to link-cost changes and to link end node failures and recoveries.A variety of quantities, including the length of messages and the average nutnber of paths affected by routing lceps, are computed as a function of time after a link or node change.Probabilities of various conditions are also obtained as a function of time, including the existence of loops.As expected, the dwtributed Belhnen-Ford algorithm behaves poorly compared with the other two.However, deciding between a routing protocol based on a link-state algorithm and one based on a loop-free d~tance-vector algorithm depends on the particular network in which it will perform.

Distributed algorithms for shortest-path problems are important in the context of routing in computer communication networks. We present a protocol that maintains the shortest-path routes in a dynamic topology, that is, in an environment where links and nodes can fail and recover at arbitrary times. The novelty of this protocol is that it avoids the bouncing effect and the looping problem that occur in the previous approaches of the distributed implementation of Bellman-Ford algorithm. The bouncing effect refers to the very long duration for convergence when failures happen or weights increase, and the nonterminating exchanges of messages, or counting-to-infinity behavior, in disconnected components of the network resulting from failures. The looping problems cause data packets to circulate and, thus, waste bandwidth. These undesirable effects are avoided without any increase in the overall message complexity of previous approaches required in the connected part of the network. The time complexity is better than the distributed Bellman-Ford algorithm encountering failures. The key idea in the implementation is to maintain only loop-free paths, and search for the shortest path only from this set.

We present a unified approach for the dynamic computation of shortest paths in a computer network using either distance vectors or link states. We describe a distributed algorithm that provides loop-free paths at every instant and extends or improves algorithms introduced previously by Chandy and Misra, Jaffe and Moss, Merlin and Segall, and the author. Our approach treats the problem of distributed shortest-path routing as one of diffusing computations, which was first proposed by Dijkstra and Scholten. We verify the loop-freedom of the new algorithm, and also demonstrate that it converges to the correct routing entries a finite time after an arbitrary sequence of topological changes. We analyze the complexity of the new algorithm when distance vectors and link states are used, and show that using distance vectors is better insofar as routing overhead is concerned.

A new distributed algorithm for the dynamic computation of the shortest paths in a computer network is presented, validated, and analyzed. According to this algorithm, each node maintains the lengths of the shortest path to each network destination and a feasibility vector. Update messages from a node are sent only to its neighbors; each such message contains one or more entries, and each entry specifies the length of the selected path to a network destination, and whether the node requires internodal coordination. The algorithms extends the Jaffe-Moss routing algorithm by allowing nodes to choose new successors to destinations with no need for internodal coordination if the new successors are considered to be at most at the same distance as the current successors. The algorithm is shown to converge in a finite time after an arbitrary sequence of topological changes, to be loop-free at every instant (independently of the delays in the network) and to outperform other previously proposed loop-free, shortest-path algorithms from the standpoint of combined temporal, message, and storage complexities.>

We present an object-oriented architecture for a computer-based, real-time, multimedia conferencing system. This architecture divides the system into five functional areas: a multimedia shared workspace, a user interface, conference management, communications, and an information base. The structure and operation of the first four areas are modeled with object-based concepts that address design requirements identified during the development of a proof-of-concept prototype, that preceded the architecture specification.

A computer-based message system (CBMS) consists of computer facilities that expedite the creation, management, and nonreal time distribution of messages. These systems are increasingly being used for formal and informal communication, supporting the distribution of textual messages. However, nontext media such as voice and graphics are very important for human interaction, and are becoming more and more important in computer system applications. As a result, there is a growing need for the support of media other than text in CBMS.Before standards for multimedia CBMS can be implemented, there are many technical issues that must be addressed. These range from the design of new mechanisms for the distribution of multimedia mail, to the design of tools needed for editing nontext media. This panel will be discussing issues encountered in the development of multimedia CBMS and an outlook for standards for multimedia computer mail.

In this paper we present an overview of an architectural model for large, distributed computer-based message systems. This model specifies 1) the organization of message systems in terms of functional entities; 2) the operation of the system; 3) the protocols and interfaces needed for interprocess communication; 4) the organization of the directory system used to support identification services. General architectural considerations related to the communications protocols for computer-based message systems are presented; these follow the general framework of the ISO model for open system interconnection. The organization and operation of the directory system are discussed in detail. Special emphasis is given to the importance of identification services in international and interconnected message systems.

In this paper we present major design considerations for the development of international computer mail protocols. A simplified functional model for computer mail systems is introduced to serve as the basis of the discussion of the protocols. The general framework of the Reference Model for Open System Architecture proposed by the ISO is followed in the description of the computer mail protocol and design issues involved at each layer of the computer mail protocol are examined. The computer mail protocol is aimed at non-interactive communication between message system users.