| Hierarchies are widely used in computer networks to help systems scale better by reducing or localizing information propagation thereby reducing message and state overhead in the network. However, simple static hierarchy construction that is commonly used does not function well in dynamic environments.; In this thesis, we explore the design and evaluation of distributed, automatic hierarchy construction techniques for large dynamic networks in the context of two diverse network application environments—the Internet and emerging pervasive computing systems that consist of many small networked devices.; In the Internet context, we present a distributed hierarchy construction algorithm that forms the basis for our scalable multicast architecture design. In our approach, a representative is chosen for each Autonomous System (AS) in the Internet. The representatives organize themselves into a hierarchy and self-configure multicast address ranges for their ASes, from which multicast groups initiated in the AS get their multicast addresses. The information about the representatives and the associated multicast address ranges is distributed throughout the Internet in a Landmark routing fashion, and is used to build inter-domain shared trees for a group. Since inter-AS routing involves resources in autonomously administered ASes, the policy constraints of ASes are considered in hierarchy construction to prevent message loops and black-holes.; In the pervasive computing context, we discuss hierarchy construction for an object-tracking sensor network that is a network of wireless sensors to monitor the location of people and everyday objects in a home or office environment. We investigate two hierarchical, self-configuring approaches for an efficient object location service. The first approach, SCOUT-AGG, is based on aggregation of object names. The second approach, SCOUT-MAP, is based on indirection, where information about an object is stored at the locator sensor for the object. SCOUT-AGG performs better for low query to mobility update rate in the system but its performance deteriorates in general relative to SCOUT-MAP as the query to update rate increases. SCOUT-MAP generally exhibits better load balancing than SCOUT-AGG for various scenarios. Simple methods to conserve energy in hierarchy construction are presented to improve network lifetime when sensors are powered by batteries. |
