Search

We propose a new framework for the link assignment (i.e., topological design) problem that arises from the use of intersatellite links (ISL's) in low-earth orbit (LEO) satellite networks. In the proposed framework, we model an LEO satellite network as a finite state automaton (FSA), where each state corresponds to an equal-length interval in the system period of the LEO satellite network. This FSA-based framework allows the link assignment problem in LEO satellite networks to be treated as a set of link assignment problems in fixed topology networks. Within this framework, we study various link assignment and routing schemes. In particular, both regular link assignment and link assignment optimized by simulated annealing are considered. For each link assignment, both static and dynamic routing schemes are considered. Our simulation results show that the optimized link assignment combined with static routing achieves the best performance in terms of both newly initiated call blocking probability and ongoing call blocking probability. The results also show that when the link assignment is the same, static routing gives better performance than dynamic routing since the latter requires a substantial amount of time to stabilize its routing table after a state transition. Index Terms - Finite state automaton, LEO satellite network, link assignment, routing, simulation.

In many recent low earth orbit (LEO) satellite networks, intersatellite links (ISLs) are used to enhance the capability of the networks. The ISLs are continuously deleted and established since the visibility between satellites changes over time. These topological changes require rerouting of the traffic on ISLs, which unavoidably involves dropping of some ongoing calls. In general, such an ongoing call dropping degrades the quality-of-service (QoS) more severely than an initiated call blocking. In this paper, we propose a call admission control scheme that allows a flexible tradeoff between dropped ongoing calls and blocked initiated calls. The call admission control scheme makes use of two techniques: traffic recasting and traffic projection. The traffic recasting maps the current traffic onto the network after the topological change whereas the traffic projection projects the recast traffic from the current time to the time of the topological change. The projected traffic is used to estimate the increase in ongoing call dropping whose QoS penalty is compared against that of increased newly initiated call blocking to make the call admission decision. Simulation results show that the proposed call admission control scheme significantly reduces the ongoing call dropping probability with only a marginal increase in the initiated call blocking and call completion probabilities. Index Terms--Call admission control, intersatellite link (ISL), link assignment, low earth orbit (LEO), routing, simulation.

Cache memory is used in almost all computer systems today to bridge the ever increasing speed gap between the processor and main memory. However, its use in multitasking computer systems introduces additional preemption delay due to the reloading of memory blocks that are replaced during preemption. This cache-related preemption delay poses a serious problem in real-time computing systems where predictability is of utmost importance. In this paper, we propose an enhanced technique for analyzing and thus bounding the cache-related preemption delay in fixed-priority preemptive scheduling focusing on instruction caching. The proposed technique improves upon previous techniques in two important ways. First, the technique takes into account the relationship between a preempted task and the set of tasks that execute during the preemption when calculating the cache-related preemption delay. Second, the technique considers the phasing of tasks to eliminate many infeasible task interactions. These two features are expressed as constraints of a linear programming problem whose solution gives a guaranteed upper bound on the cache-related preemption delay. This paper also compares the proposed technique with previous techniques using randomly generated task sets. The results show that the improvement on the worst-case response time prediction by the proposed technique over previous techniques ranges between 5 percent and 18 percent depending on the cache refill time when the task set utilization is 0.6. The results also show that as the cache refill time increases, the improvement increases, which indicates that accurate prediction of cache-related preemption delay by the proposed technique becomes increasingly important if the current trend of widening speed gap between the processor and main memory continues. [ABSTRACT FROM AUTHOR]