Institute for Systems Research Technical Reports
Permanent URI for this collectionhttp://hdl.handle.net/1903/4376
This archive contains a collection of reports generated by the faculty and students of the Institute for Systems Research (ISR), a permanent, interdisciplinary research unit in the A. James Clark School of Engineering at the University of Maryland. ISR-based projects are conducted through partnerships with industry and government, bringing together faculty and students from multiple academic departments and colleges across the university.
Browse
Search Results
Item A Local Optimization Algorithm for Logical Topology Design and Traffic Grooming in IP over WDM Networks(2003) Lee, Kwang-Il; Shayman, Mark; ISRIn this paper we investigate logical topology design algorithms using local optimization technique. Since the problem of the optimal logical topology design for all traffic demands is NP-complete, we design a logical topology by sequentially constructing the shortest path for one source-destination pair at a time. The path is a locally optimized path in the sense that there are no other paths with less hop count that may be constructed from existing links and newly created links. For this we define an Estimated Logical Hop Count (ELH), which is the shortest logical hop count for a given source and destination when it is applied. Also, we propose two heuristic logical topology design algorithms making use of ELH: ELH with Maximum Traffic Demands (MTD) and with Resource Efficiency Factor (REF). Finally, we evaluate the performance of the proposed algorithms by GLASS/SSF simulator. The simulation results show that ELH with REF outperforms other well-known algorithms in terms of the weighted hop count and network throughput.Item Integrated Logical Topology Design and Traffic Grooming in Re-Configurable WDM Networks(2002) Lee, Kwang-Il; Sudarsan, Lakshmi; Shayman, Mark; ISRWavelength-division multiplexing (WDM) networks provide reconfigurability and the possibility of creating single hop communication channels between end nodes. This eliminates the electronic processing at intermediate nodes and reduces delay significantly.However, because of the limited number of network interfaces and other scalability issues, single hop channels do not support all traffic demands. Some of the traffic requires routing or switching over multi-hop lightpaths to reach the destination. Such traffic is referred to as multi-hop traffic. The optimization of multi-hop traffic has significant impact on the performance of optical networks.
In this paper, we propose an integrated logical topology design and traffic-grooming algorithm for the optimization of the multi-hop traffic. This is enabled by the multi-hop lighpath setup mechanism, which is to establish lightpaths from/to intermediate nodes to/from end nodes for multi-hop traffic.
The proposed algorithm considers traffic grooming for multi-hop traffic when the logical topology is designed and always gives high priority to high traffic demands when allocating network resources. Consequently, it leads to low delay and to high network throughput. Simulations indicate that the proposed algorithm has substantial improvement in terms of the average weighted hop distance and network throughput in comparison with known algorithms such as HLDA, MMHA and MRU.
Item Multi-time Scale Markov Decision Processes(2002) Chang, Hyeong Soo; Fard, Pedram; Marcus, Steven I.; Shayman, Mark; Marcus, Steven I.; Shayman, Mark; ISRThis paper proposes a simple analytical model called M time-scale MarkovDecision Process (MMDP) for hierarchically structured sequential decision making processes, where decisions in each level in the M-level hierarchy are made in M different time-scales.In this model, the state space and the control space ofeach level in the hierarchy are non-overlapping with those of the other levels, respectively, and the hierarchy is structured in a "pyramid" sense such that a decision made at level m (slower time-scale) state and/or the state will affect the evolutionary decision making process of the lower level m+1 (faster time-scale) until a new decision is made at the higher level but the lower level decisions themselves do not affect the higher level's transition dynamics. The performance produced by the lower level's decisions will affect the higher level's decisions.
A hierarchical objective function is defined such that the finite-horizon value of following a (nonstationary) policy at the level m+1 over a decision epoch of the level m plus an immediate reward at the level m is the single step reward for the level m decision making process. From this we define "multi-level optimal value function" and derive "multi-level optimality equation."
We discuss how to solve MMDPs exactly or approximately and also study heuristic on-line methods to solve MMDPs. Finally, we give some example control problems that can be modeled as MMDPs.