Other Free Encyclopedias » Online Encyclopedia » Encyclopedia - Featured Articles » Contributed Topics from A-E

Data Discovery, Routing and Traffic Patterns - Routing Protocols, Storage-Retrieval of Dynamic Content, Traffic Patterns and Information Associations

based mobility networks rendezvous

Definition: Resource discovery and rendezvous mechanisms are necessary to dynamically locate media servers (e.g., the nearest or best servers), data storages, membership servers (for multicast sessions), or peers (e.g., other users) for direct connections.

In general, the resource discovery module of CHaMeLeoN can be categorized as either ‘location-aware’ or ‘location-free’. Location-aware architectures require availability of location information. They typically use geographic or trajectory routing to forward the updates or queries and include geographic rendezvous mechanisms (such as GLS, Rendezvous Regions , and GHT) and trajectory advertisement schemes (such as TBF). In location-aware networks, geographic-based distributed hash tables are utilized to efficiently establish content based routing schemes.

In earlier work, we designed a geographic rendezvous mechanism based on rendezvous regions. In this architecture, the network is divided into regions, and the resource key space (e.g., file space) is divided into prefixes. Each resource prefixes maps into a region. The mapping can be discovered dynamically using a bootstrap mechanism. We have shown that using regions (instead of locations as in GHT) is robust to mobility and location inaccuracy effects. Furthermore, the performance of the rendezvous architecture depends on the data semantics and access pattern. For example, for media servers, where there is a high lookup-to-insertion ratio (meaning the media is accessed many times per storage), the Rendezvous Regions scheme produces far fewer messages (over 80% less) when compared with GHT, and achieves near perfect success rate. Hence, it is important to tailor the rendezvous mechanism to the application characteristics (e.g., lookup-to-insertion ratio). Characterizing applications, data semantics and access patterns is of key interest. Matching rendezvous architectures to application classes, and designing new (adaptive) rendezvous mechanisms are additional challenges that need to be addressed in future work.

Location-free discovery architectures do not use location information. Some of the main approaches include flooding-based techniques, on-demand routing with caching, hierarchical and hybrid routing. Flooding techniques include simple flooding (or expanding ring search), scoped flooding, and efficient reduced broadcast. Hierarchical routing includes cluster-based, landmark, and dominating set approaches. Hybrid routing includes zone routing and contact-based architectures. We have extensively studied these techniques. Our studies show that a loose hierarchy (using zones) coupled with ‘contacts’ achieves the best performance in terms of bandwidth and energy efficiency for the same success rates. The advantage of this scheme is most prominent for high-activity networks, where the query-to-mobility ratio is high since the cost of establishing and maintaining the hierarchy is amortized across savings in query cost. While route caching schemes are also useful in some scenarios, our studies have shown that the overhead of maintaining the cache up to date may outweigh its benefits for small transfers and high mobility show that for small transfers and high mobility caching validity may limit the efficacy of caching. Resource discovery may also be coupled with routing. For example, ZRP and the contact-based mechanisms are easily combined into one architecture, in which ZRP is used for route discovery while contact-based mechanisms are used for resource discovery (possibly over sub-optimal routes but with very high efficiency).

Routing Protocols

In order to sustain data delivery with least disruption, routing protocols must adapt seamlessly to mobility. Pure proactive approaches (e.g., DSDV) may incur high overhead and may not be able to cope with high mobility scenarios. On the other hand reactive protocols (e.g., DSR and AODV) incur much less overhead and are suitable for small/medium networks (<100 nodes), but also incur delivery disruption due to link failures and route maintenance. Hybrid protocols (e.g., ZRP) uses proactive routing Page 141  within for nearby nodes (within the zone) and reactive routing discovery for nodes beyond the zone. ZRP is suitable for larger networks (>100 nodes) but also suffers packet loss with link failures. We intend to investigate the use of reactive route discovery with proactive route maintenance in CHaMeLeoN. Such schemes are bandwidth efficient and able to proactively discover new routes before the existing ones break. This investigation borrows from existing work in this area in addition to designing new mechanisms.

Dynamic content, generated by real-time communications, will often be delivered to a group of participants in a session. The mode of communication depends on the definition of the ‘group’. For dynamically created logical groups, multicast may be used for efficient communication. For ad hoc networks, in general, mesh-based multicast routing is more robust to network dynamics than tree-based routing. This is at the expense of increased overhead. For geographically defined groups, geocast may be used. For locating either any or nearest participant, anycast may be used. Finally, manycast may be used for locating k out of n participants. Hence, routing and transport protocols are needed to support such applications. Dynamics of the multicast group membership (whether in terms of senders/producers or receivers/consumers) would have a great impact on the performance of the various protocols and hence on the quality of data delivery. Dealing with dynamics of membership, traffic patterns, and mobility are issues we address in the routing and protocol design and evaluation phases of CHaMeLeoN.

Storage-Retrieval of Dynamic Content

When dynamic content is to be stored for future retrieval, issues of dynamic storage, indexing, querying and retrieval must be addressed. Resource and data discovery architectures are needed to facilitate server (or file) location by the interested parties without having to flood the request throughout the network. Such storage-retrieval architecture should be self-configuring, scalable and robust to network dynamics (including mobility). They impact the data placement issues discussed previously.

In the design of the above protocols, including resource discovery and multicast protocols, modeling and analysis of user and information association are essential. Association analysis captures traffic and access patterns within groups of nodes. Associations and traffic patterns depend on the nature of the application. The network nodes can be either dedicated to users or can be autonomous (e.g., as in sensor networks). With CHaMeLeoN, we are interested in two types of associations: (a) small world friend associations in user-centric networks (such as wireless classrooms or collaboration using ad hoc networks), and (b) data correlation in data-centric sensor networks.

This analysis will facilitate the design of traffic prediction (and subsequently data placement) schemes to improve the performance and availability of data. In addition, mobility prediction schemes will facilitate seamless delivery of data. We shall address mobility based schemes in research in the following section.

Traffic Patterns and Information Associations

CHaMeLeoN may utilize traditional address-centric (or user-centric) paradigms to associate devices with information. A data-centric approach may also be feasible and must be investigated further. We describe each in turn.

With a user-centric approach, users establish communities that manifest association of conversation, file sharing, trust, correlated mobility or common interests. We have been investigating these social behaviors and the concept of friends in wireless networks using the small world’s models. Small worlds refer to classes of graphs that exhibit high clustering similar to that of regular graphs, but a low average path length (i.e., degree of separation) similar to that of random graphs. Small world graphs have been observed in many contexts of human behavior, in security (PGP) associations, web links, and interest groups, among others. By understanding such social underpinnings, we shall develop a better and deeper understanding of correlated access patterns, mobility, security and other network associations. This will result in efficient networking protocols. Moreover, we aim to achieve desirable characteristics of small worlds by constructing carefully chosen short cuts to bridge the gap between otherwise distant clusters of users or information. One example of such structure is building a small world of trust to establish security associations efficiently in large-scale wireless networks. We shall focus on understanding information associations in wireless classrooms as one of our target applications.

Data-centric paradigms apply to sensor networks where the physical phenomena monitored produces data that is observed/recorded by multiple sensors. Hence sensor readings may be correlated. Sometimes the physical phenomenon propagates according to well-known diffusion laws, creating natural spatio-temporal gradients of information in the sensor network. This may relate to protocol design and in-network processing with CHaMeLeoN, e.g., using data aggregation or gradient based routing.

Data Encryption Standard (DES) and Advanced Encryption Standard (AES) [next] [back] Dash, Julie (1952–)

User Comments

Your email address will be altered so spam harvesting bots can't read it easily.
Hide my email completely instead?

Cancel or