Institute for Systems Research
Permanent URI for this communityhttp://hdl.handle.net/1903/4375
Browse
Search Results
Item Multicast Routing and Resource Allocation in a Mobile Wireless Network Like the Digital Battlefield(1997) Bhattacharya, Rupla; Ephremides, Anthony; ISR; CSHCNﲍulticasting refers to the transmission of the same information to several destinations. In this paper we are addressing the issue of multicast routing in a wireless network that consists of an arbitrarily large number of nodes, each of which is mobile in an unpredictable manner. Most existing multicast algorithms have been developed for non-wireless, stationary networks in which there is an abundance of bandwidth and where intended destinations initiate their connection to the multicast tree. In the Digital Battlefield of the future, bandwidth may be limited if not scarce and, in addition to destination-initiated connections, there will be purely source-initiated multicasts that correspond to typical command or reconnaissance messages. In this paper, we establish the beginnings of a complete multicast algorithm that is capable of adapting to topological changes. More importantly, the algorithm is combined with dynamic channel allocation procedures that are capable of reassigning bandwidth resources on an as-needed basis throughout the network. Power control is applied to tradeoff between routing delays and number of connection requests satisfied. The goal of the algorithm is to establish and maintain the maximum number of connection requests while making efficient use of available bandwidth and avoiding congestion which might lead to network collapse.Item Fault Tolerant Rerouting in Broadband Multiclass Networks(1996) Vakhutinsky, A.I.; Ball, M.O.; ISR; CSHCNModern broadband integrated service digital networks (B-ISDN) must handle multiclass traffic with diverse quality of service (QOS) requirements. The main purpose of our research is to design call rerouting mechanisms which provide rapid restoration of network services in case of link failures. We suggest two approaches: Virtual circuit (VC) and virtual path (VP) reroutings. The first approach is more reactive while the latter is more proactive. The applicability conditions for the first approach include the availability of a layered network structure similar to VC/VP architecture which is widely accepted in asynchronous transfer mode (ATM) networks. Another applicability condition is the extent of network failure: VP level restoration is designed for single link failures - the most common in the telecommunication networks. On the other hand, in case of less predictable multiple link failures, VC-level rerouting is appropriate. These two rerouting approaches vary in the amount of time required to carry them out. Though both schemes are designed to work in real time, VP-level rerouting tends to be faster and can be performed in an on-line mode using pre-computed paths. VC- level rerouting requires real-time computation of routes which may result in a noticeable impact on some services. On the other hand, VP-level rerouting requires a substantial amount of off- line computation to design the VP layout and the backup routes.In this dissertation we propose a new model and associated algorithms to solve a VC-rerouting problem in real time. This model takes advantage of the distributed network data and computational resources by decomposing the problem at an early stage and then performing the computations in a decentralized mode.
In order to solve the fault tolerant VP layout problem, we formulate a bi-criteria optimization model reflecting the tradeoff between throughput and certain QOS requirements. The model involves a piece-wise linear approximation to the capacity allocation rule for variable bit rate connections statistically multiplexed over a VP.
Both models are formulated as integer programs. The solution method developed employ relaxation and aggregation of variables, feasible solution heuristics and valid inequalities. The results of the computational experiments presented indicate that the methods developed are efficient and produce accurate solutions.
Item Call Rerouting in an ATM Environment(1995) Ball, Michael O.; Vakhutinsky, A.; ISR; CSHCNATM networks must handle multiclass traffic with diverse quality of service requirements. We consider a multiclass routing model in which routes are calculated in a distributed fashion by the call origination nodes. Within this general context, we address the problem of rerouting a set of previously routed calls to avoid a failed link. Under the approach we propose, a single node executes an aggregate global rerouting of all affected calls and then converts the set of aggregate routes into an allocation of bandwidth on each link to call origination nodes for the purpose of rerouting. The bandwidth allocation is distributed to each origination node, which in turn then calculates routes for the individual calls. The problem faced by each call origination node is a variant of the so-called bandwidth packing problem. We develop and analyze an approximate algorithm for solving the problem in the specific context that arises in our setting.Item Dynamic Routing of Voice/Data-Integrated and ATM-based Hybrid Networks(1994) Chen, Shihwei; Baras, John S.; ISR; CSHCNA hybrid network consisting of a satellite network and a terrestrial network will increase the overall network efficiency considerably by using all available resources and media. This dissertation considers dynamic routing in both voice/data- integrated and ATM-based hybrid networks.Optimal dynamic routing in such mixed-media (voice/data-integrated) networks under Markov Queueing Modeling has been developed and solved. Routing problems in such a domain usually lead to a weighted-sum minimization or a minimax problem. A new approach to obtain the trade-off curve of multiple-objective optimization is outlined. With a numerical optimization package, we can plot the trade-off curve exactly.
Both a centralized and a distributed implementation of this problem with Kalman filter techniques and Equilibrium Programming are presented. These techniques allow the control of a large and stochastic network by communicating with a group of communication managers in a parallel manner.
For ATM- based hybrid networks, an economic model with the objective of maximizing the ﲳocial welfare has been adapted. This model can be developed into a form of a two-player game. With a little modification and adaptation, we will be able to solve the joint problem of access control and routing in both the weighted-sum formulation and the economic formulation.