This paper studies the problem of constructing maximum-lifetime data aggregation trees in wireless sensor networks for collecting sensor readings. This problem is known to be NP-hard. Wireless sensor networks in which transmission power levels of sensors are adjustable and heterogeneous are considered. An approximation algorithm is developed to construct a data aggregation tree whose inverse lifetime is guaranteed to be within a bound from the optimal one. Adjustable transmission power levels of the sensors introduce an additional term in the bound compared with the bound for networks in which transmission power levels of all sensors are fixed. The additional term is proportional to the difference between the maximum and minimum amounts of energy for a sensor to transmit a message using respectively its maximum and minimum transmission power levels. The proposed algorithm is further enhanced to obtain an improved version. Simulation results show that properly adjusting transmission power levels of the sensors yields higher lifetime of the network than keeping their transmission power levels at the maximum level.

This paper studies the problem of constructing a minimum-cost multicast tree (or Steiner tree) in which each node is associated with a cost that is dependent on its degree in the multicast tree. The cost of a node may depend on its degree in the multicast tree due to a number of reasons. For example, a node may need to perform various processing for sending messages to each of its neighbors in the multicast tree. Thus, the overhead for processing the messages increases as the number of neighbors increases. This paper devises a novel technique to deal with the degree-dependent node costs and applies the technique to develop an approximation algorithm for the degree-dependent node-weighted Steiner tree problem. The bound on the cost of the tree constructed by the proposed approximation algorithm is derived to be (2lnk/2 +1)(WT*+B), where k is the size of the set of multicast members, WT*is the cost of a minimum-cost Steiner tree T*, and B is related to the degree-dependent node costs. Simulations are carried out to study the performance of the proposed algorithm. A distributed implementation of the proposed algorithm is presented. In addition, the proposed algorithm is generalized to solve the degree-dependent node-weighted constrained forest problem.

This paper studies the problem of constructing application-layer multicast trees for end-system based voice conferences in which voice mixing and replication are performed at end systems. This problem is formulated as a degree-constrained node-weighted Steiner tree problem with a degree-dependent cost associated with each node, which is a generalization of the degree-constrained node-weighted Steiner tree problem with a fixed cost associated with each node. This paper devises a novel technique to deal with degree-dependent nodal costs and develops a bicriteria approximation algorithm, with the degree of each node and the cost of the tree as two objectives, for this more general Steiner tree problem. The bound on the degree of each node and the bound on the cost of the tree constructed by the bicriteria approximation algorithm are derived. Two heuristic algorithms which construct multicast trees that obey the degree constraint on each node are obtained by modifying the bicriteria approximation algorithm. The performances of the two heuristic algorithms are studied via simulations.

This paper studies the problem of constructing a minimum-cost multicast tree (or Seiner tree) in which each node is associated with a cost that is dependent on the degree of the node on the multicast tree. The cost of a node may depend on its degree on the multicast tree due to a number of reasons. For example, a node may need to perform various processing for sending messages to each of its neighbors on the multicast tree. Thus, the overhead for processing the messages increases as the number of neighbors increases. This paper devises a novel technique to deal with the degree-dependent node costs and applies the technique to develop an approximation algorithm for the problem. The bound on the cost of the multicast tree constructed by the proposed approximation algorithm is derived.

This paper proposes a distributed location management strategy called weighted sliding-frame strategy for wireless mobile networks in which the processing speeds of the location information databases (LIDs) are heterogeneous. In the proposed strategy, a number of consecutively numbered location information databases are arranged into a frame. A frame of location information databases overlaps with the next frame except one database. Each frame is assigned a weight which is used to distribute the location information of the mobile hosts among the frames. The number of mobile hosts whose location information are stored in a frame is proportional to the weight assigned the frame. A nonlinear convex programming problem is formulated and solved numerically in order to find the set of weights that minimize the average database response time. Our numerical results show that the proposed weighted sliding-frame strategy is able to properly distribute the location information of the mobile hosts among the frames such that the average database response time is significantly lower than that of the sliding-frame strategy proposed in our previous work.

This paper studies the problem of constructing maximum-lifetime data gathering trees in sensor networks in which the power levels of sensors are heterogeneous and adjustable. In-network data aggregation is also employed to aggregate sensor data while they are being forwarded toward the base station. For sensor networks in which sensors have fixed and the same transmission power level, Wu et al. has derived an upper bound on the lifetime of the optimal data gathering tree and developed an approximation algorithm for constructing data gathering trees. The model considered in this paper is more general than that considered by Wu et al. in that the transmission power levels of sensors are heterogeneous and adjustable. For this more general model, this paper derives an upper bound on the lifetime of the optimal data gathering tree. Given an initial tree, an algorithm is developed to construct a data gathering tree by iteratively rearranging the current tree and improving the lifetime of the current tree. The worst-case computational complexity of the algorithm is shown to be polynomial.

This paper considers the problem of constructing minimum-delay multicast trees for message dissemination in overlay networks in which nodal delays for processing messages are taken into account in addition to communication delays. The objective is to find a multicast tree to deliver a message from a source to multiple destinations in minimum delay time. This paper introduces a new delay measure called reception-and-processing delay that takes nodal processing delays into account for constructing multicast trees. In the process of constructing a multicast tree, the branches of the multicast tree may intersect or overlap with each other. An efficient method is devised to avoid this undesirable phenomenon. Several heuristic algorithms are developed for constructing multicast trees. The performances of the heuristic algorithms are studied via simulation. Our simulation results show that constructing the multicast tree by iteratively attaching the destination node with the smallest reception-and-processing delay to the current multicast tree yields the lowest average multicast delay among the heuristic algorithms studied in this paper.

The non-collision packet reservation multiple access (NC-PRMA) protocol was proposed by Wen and Wang to eliminate the unstable phenomenon in the PRMA protocol under heavy load conditions by allocating dedicated control mini-slots to mobile terminals (MTs). However, this does not utilise the channel resource efficiently. A dynamic non-collision PRMA (DNC-PRMA) protocol has been proposed to dynamically allocate control mini-slots to MTs such that the channel resource can be utilised efficiently. Using simulation, the proposed DNC-PRMA protocol is shown to yield significantly higher channel utilisation, lower packet dropping probability and lower channel access delay than a protocol that allocates a dedicated mini-slot to each MT.

This paper proposes a new fixed-alternate routing algorithm for all-optical WDM networks without wavelength conversion in order to reduce the connection blocking probability. The key idea in the proposed fixed-alternate routing algorithm is to try to route the traffics in approximately the optimal way. The multiple routing paths between each source-destination pair are arranged and used in descending order according to the traffic intensities obtained by solving a nonlinear multicommodity flow optimization problem. It is well known that finding the connection blocking probability is a very difficult task. Therefore, an objective function closely related to the connection probability is devised and used to formulate a nonlinear multicommodity flow optimization problem. Simulations are performed to study the performance of the proposed fixed-alternate routing algorithm. Our simulation results show that sorting the routing paths according to the optimally assigned traffic intensities in the proposed fixed-alternate routing algorithm can effectively reduce the connection blocking probability compared with sorting the routing paths according to hop counts in a typical fixed-alternate routing algorithm. In general, in all-optical WDM networks, a connection request that goes through a longer path experiences higher connection blocking probability than a connection request that goes through a shorter path. This is known as the fairness problem. Our simulation results show that the proposed algorithm yields better fairness than a typical fixed-alternate routing algorithm.

In all-optical WDM networks, splitters at branch nodes are used to realize multicast trees. It is expensive to place splitters at all of the nodes in an all-optical WDM network. To reduce the cost, splitters can be placed at a subset of nodes. The problem of selecting a subset of nodes to place the splitters such that certain performance measure is optimized is called the splitter placement problem. Splitter placement problems in all-optical WDM networks in which a single light tree is constructed to realize each multicast connection have been studied in previous researches. This paper studies the splitter placement problem in all-optical WDM networks in which a light forest consisting of a collection of light trees is used to realize a multicast connection. The goal is to place a given number of splitters in the network such that the average per link wavelength resource usage of multicast connections is minimized. An upper bound and a lower bound on the per link average wavelength resource usage for a given number of multicast connections are derived. Two splitter placement methods are proposed for this problem. The two proposed splitter methods are shown to yield significant lower average wavelength resource usage than the random placement method. One of the methods is shown to produce near minimum average wavelength resource usage.

Link failure is one of the most critical network fault conditions. Relying solely on SNMP traps to detect and identify link failures is not a complete solution. To supplement the SNMP-trap mechanism, one or more detectors can be placed in the network to periodically poll the devices using the ping or traceroute utilities such that all links are under the surveillance of the detectors. The goal is to place the smallest number of detectors to have all of the links under surveillance such that the cost of placing detectors in the network is reduced. In this paper, this problem is formulated as a minimum set covering problem. A new heuristic algorithm is proposed for this problem. Simulations are performed to study the performance of the proposed heuristic algorithm.

In reservation-based packet scheduling algorithms for single-hop WDM networks, one of the wavelengths is used as a control channel which is shared by all of the nodes for transmitting reservation information. Time on the control channel is divided into control frames of fixed length. Each of the control frames is further divided into a number of control slots. Before transmitting a data packet, a node sends a control packet in a control slot to inform all other nodes of its intention to send a data packet. The data packet can then be scheduled for transmission. Each of the nodes in the system is assigned a dedicated control slot. Free control slots in the control frames cannot be used by other nodes. The control packets generated by those nodes that have more data packets to send must be transmitted in the next or later control frames although there are a number of free control slots. The result of delaying the transmissions of control packets is increased packet delays. This effect has significant impact on packet delays under nonuniform traffics. To increase the utilization of the control slots and reduce the packet delays, we propose to adjust the lengths of the control frames dynamically according to the traffic patterns of the nodes. We propose a dynamic control frame structure with variable number of control slots. A scheme is devised to enable the nodes in the network to dynamically acquire and release control slots depending on their loads. Thus, the control frames will include only necessary control slots for those nodes that have or potentially have data packets to send. Therefore, the control slots on the control channel can be used efficiently and the packet delays can be reduced. Simulations are performed to study the performance of the proposed dynamic control frame structure. Our simulation results show that dynamically adjusting the lengths of the control frames can effectively increase the utilization of the control slots and reduce the mean packet delay under nonuniform traffic compared with using fixed-length control frames.

To support server-based reliable multicast, repair servers are used to store packets from sender(s) such that lost packets can be retransmitted to receivers from the repair servers. A repair server can be a specially designed host co-located with a router or a router with the functions of a repair server integrated in it. It may not be practical to place a repair server at each of the routers in the network if the size of the network is large. It is more economical to place repair servers at a subset of the nodes in the network such that the placement is cost-effective. Improper placement of repair servers may result in low utilization of the repair servers. It is desirable to place repair servers in the network such that they can be used effectively. Given a number of repair servers, we want to find a subset of the nodes in the network to place the repair servers such that the repair servers can be used effectively. To our knowledge, this problem has not been studied in previous researches. We propose three methods for the placement of repair servers. The performance of the three proposed methods are compared with that of a method which place the repair servers randomly in the network. Our simulation results show that the three proposed methods yield significant better performance than the random placement method. One of the three proposed methods, namely, k-maximum path count method, produces the best performance among the three proposed methods.

This paper shows that, for single-hop WDM networks, a multicast scheduling algorithm which always tries to partition a multicast transmission into multiple unicast or multicast transmissions may not always produce lower mean packet delay than a multicast scheduling algorithm which does not partition multicast transmissions. The performance of a multicast scheduling algorithm may depend on the traffic conditions and the availability of the channel resource in the network. A hybrid multicast scheduling algorithm that can produce good performance for wide ranges of the traffic conditions and the availability of the channel resource in the network is proposed. Depending on the average utilizations of the data channels and the receivers, the proposed hybrid multicast scheduling algorithm dynamically chooses to employ a multicast scheduling algorithm which always tries to partition multicast transmissions or a multicast scheduling algorithm which does not partition multicast transmissions. Extensive simulations are performed to study the performance of the proposed hybrid algorithm. Our simulation results show that the proposed hybrid algorithm produces lower mean packet delay for wide ranges of the load, the maximum multicast group size, the percentage of unicast traffic, and the number of data channels in the network compared with a multicast scheduling algorithm which always tries to partition multicast transmissions and a multicast scheduling which does not partition multicast transmissions.

The problem of minimizing the number of transmissions for a multicast transmission under the condition that the packet delay is minimum in single-hop WDM networks is studied in this paper. This problem is proved to be NP-complete. A heuristic multicast scheduling algorithm is proposed for this problem. The performance of the proposed scheduling algorithm is compared with two other multicast scheduling algorithms by extensive simulations. Our simulation results show that (i) the proposed heuristic algorithm always produces lower mean packet delay than the other two algorithms, and (ii) an algorithm which partitions a multicast transmission into multiple unicast or multicast transmissions may not always produce lower mean packet delay than the algorithm which does not partition a multicast transmission into multiple transmissions when the number of data channels in the system is limited.

Network topology information is useful for network administration and planning. Techniques for automatic generation of the network layer topology maps of IP networks have been proposed by Lin, Lai and Chen (see Proc. of IEEE ICC, 1998), by Mansfield, Ouchi, Jayanthi, Kimura, Ohta and Nemoto (see Proc. of IEEE INFOCOM, p.473-80, 1996) and by Schonwalder and Langendorfer (1993). The devices in a subnet can be found using a network layer topology discovery tool. However, the link layer topology of the subnet can not be obtained by a network layer topology discovery tool. An algorithm for automatic discovery of the link layer topology of an IP subnet is proposed in this paper. The algorithm uses the link layer topology configuration information obtained from various sources including the MIBs in routers, bridges, and switches, the Internet Control Message Protocol (ICMP), the Domain Name System (DNS), and etc. to produce the link layer topology map. The proposed link layer topology discovery algorithm has been implemented based on the Tcl/Tk and Scotty environment.

This paper describes the MIB objects in the ATM-MIB module defined in RFC1695 and the Fore-Switch-MIB module defined by Fore Systems Incorporated which are useful in automatic discovery of ATM network topologies and tracing ATM virtual connections. The key ideas for automatic topology discovery and virtual connection trace for ATM networks are presented. We have implemented an ATM topology discovery tool and a virtual connection trace tool using the Tcl language on a Sun workstation.

A topology discovery algorithm for IP networks is proposed. Topology configuration information can be obtained from various sources including the MIBs in routers and gateways, the Internet Control Message Protocol (ICMP), the traceroute program, the Domain Name System (DNS), and etc. In order to retrieve the MIB information in a router, the IP address of the router has to be known. However, the IP addresses of the routers in the network of interest may not be known in advance. This paper presents an algorithm for automatic topology discovery under the situation that the IP addresses of the routers are not known in advance. Detailed implementation techniques for bringing pieces of the information together to produce a topology map are discussed.

In this paper, the dynamic multicast routing problem is studied. The multicast routing problem has been shown to be NP-complete. Many heuristics have been proposed to find the multicast trees for multicast connections. In computer networks, application services may allow nodes to join or leave the multicast connection dynamically. The multicast routing problem in which nodes are allowed to join or leave the multicast connection is called the dynamic multicast routing problem. A new dynamic multicast routing algorithm called virtual trunk dynamic multicast (VTDM) routing algorithm is proposed for this problem. A virtual trunk (VT) is a tree of the underlying graph. It is used as a template for constructing multicast trees. The VTDM routing algorithm constructs multicast trees based on the virtual trunk. Simulations are performed to study the performance of the VTDM routing algorithm. Simulation results show that the performance of the VTDM algorithm is close to that of the KMB algorithm (a near optimal heuristic for the static multicast routing problem).

This paper presents an accurate analytical model for evaluating the performance of the join the shortest queue (JSQ) policy. The system considered consists of N identical queues each of which may have single or multiple servers. A birth-death Markov process is used to model the evolution of the number of jobs in the system. Our results show that this method provides very accurate estimates of the average job response times.

Exact performance analyses of dynamic load-balancing policies for distributed systems are very difficult because the state space is multidimensional and load-balancing decisions are state-dependent. A state-aggregation method is proposed to analyze the performance of dynamic load-balancing policies. Those states with the same number of jobs are aggregated into a single state. The number of jobs in the system is modeled by a birth-death Markov process. The state transition rates are estimated by an iterative procedure. The proposed state-aggregation method is applied to analyze the performance of a particular dynamic load-balancing policy, namely a symmetric policy with threshold value equal to one. Extensive simulations were performed to study the accuracy of the state-aggregation method. This method provides accurate performance estimates for the symmetric policy for systems of various sizes when the mean job transfer delay is small compared to the average job service time.>

An analytical method is developed to analyze the performance of the join the shortest queue (JSQ) policy for systems with N identical queues, N>or=2. No simulation result is used to refine the analytical model. A birth-death Markov process is used to model the evolution of the total number of jobs in the system. An iterative procedure is developed to estimate the average service rates for different states. The average job response time is then obtained. Extensive simulations are performed to study the accuracy of the analysis. Results show that this method provides estimates within 3.5% of the average job response times for N up to 64.>

A dynamic load-balancing policy is proposed with a central job dispatcher called the LBC policy for distributed systems. The design of this policy is motivated by the operation of a single-queue multiserver queueing system, and the average job response time is the same as that of a single-queue multiserver system, which is the best achievable performance when the communication delay is reduced to zero. Hence, near-minimum average job response time is expected for distributed systems with high-speed communication subnets. The performance is studied for systems with nonnegligible job transfer delays in the following three aspects: average job response time, overhead due to information exchanges, and sensitivity to heterogeneous load.>

A dynamic load balancing policy with a central job dispatcher, called the LBC policy, is proposed for distributed systems. The design of this policy is motivated by the operation of a single-queue-multi-server queuing system. The average job response time of this policy is the same as that of a single-queue-multi-server system which is the best achievable performance when the communication delay is reduced to zero. Hence, this policy is expected to provide near minimum average job response time for distributed systems with high-speed communication subnets. The performance of this policy is studied for systems with non-negligible job transfer delays in the following three aspects: average job response time, overhead due to information exchanges, and sensitivity to heterogeneous load.>

A study is made of three dynamic load balancing policies in distributed systems with service interruptions, namely, sender initiated, receiver initiated, and a combination of the two, in different cases: performing and not performing load-balancing functions while the computers are in the middle of interruptions. The policies are analyzed by using decomposition approximation and matrix-geometric solution techniques. Simulations are used to validate the analytical results. The policies are compared to each other and to no load balancing. Sensitivities of the performance to the characteristics of interruptions and design parameters are studied. It is concluded that load balancing has a significant advantage in improving performance. Performing load-balancing functions while the computers are in the middle of interruptions also provides considerable performance improvement.>

The load balancing and routing problems are combined as a single problem to capture the interaction between them. An optimization problem for joint load balancing and routing is formulated using a linear combination of the average job response time and average message delay as the performance criterion. Given an initial feasible solution, the Frank-Wolfe method is applied to solve the problem. An algorithm which gives an optimal solution is obtained. The algorithm is then extended to solve the same problem with multiple types of jobs.>