Efficient Scheduling Algorithms for Real-Time Service on WDM Optical Networks

One of the important issues in the design of future generation high-speed networks is the provision of real-time services to different types of traffic with various time constraints. In this paper we study the problem of providing real-time service to hard and soft real-time messages in Wavelength-Division-Multiplexing (WDM) optical networks. We propose a set of scheduling algorithms which prioritize and manage message transmissions in single-hop WDM passive star networks based on specific message time constraints. In particular, we develop time-based priority schemes for scheduling message transmissions in order to increase the real-time performance of a WDM network topology. We formulated an analytical model and conducted extensive discrete-event simulations to evaluate the performance of the proposed algorithms. We compared their performances with that of the state-of-the-art WDM scheduling algorithms which typically do not consider the time constraint of the transmitted messages. This study suggests that when scheduling real-time messages in WDM networks, one has to consider not only the problem of resources allocation in the network but also the problem of sequencing messages based on their time constraints.     

Effects of a Priority Discipline in Routing for Packet-Switched Networks

This paper addresses itself to some comparisons of adaptive routing algorithms in store-and-forward Communication nets. The intent here is to demonstrate how some relatively simple add-ons to already existing adaptive algorithms can decrease the average message delay and increase message throughput in the network. The overview of many existing routing algorithms is intended to point out that, although an algorithm may be adaptive, it is not necessarily good in terms of the performance measures addressed in this paper. The basic objective of this study is to assess the effects of endogenous priority assignment to messages that have reached some specified aging threshold while in the network and to note the effects of Such priority assignment on network performance. The performance measures are average message delay, throughput, and number of messages undelivered. The routing techniques are demonstrated via simulation on an 8node highly connected network and a 19-node Advanced Research Projects Agency (ARPA) network. The routing algorithms are applied with and without network element destruction on the selected networks.     

A cost-based scheduling algorithm for differentiated service on WDM optical networks

One of the important issues in the design of future generation of high-speed networks is to provide differentiated services to different types of traffic with various time constraints. We propose an adaptive scheme to manage message transmission in single-hop passive-star coupler based wavelength-division multiplexing (WDM) optical networks. This study suggests that when scheduling message transmission in WDM networks a differentiated service should be considered in order to meet the time constraint to transmission of real-time messages while non real-time messages are being served so that the overall performance of the network could be improved.     

RAA: a ring-based address autoconfiguration protocol in mobile ad hoc networks

The problem for dynamic IP address assignment is manifest in mobile ad hoc networks, especially in 4G all-IP-based heterogeneous networks. Existing solutions are mainly riveted to decentralized algorithms, applying a large number of broadcast messages to (1) maintain available IP address pools and (2) ensure no address duplication occurring. In this paper, we propose a ring-based address autoconfiguration protocol to configure node addresses. This work aims at the decentralized ring-based address autoconfiguration (DRAA) protocol, which has the advantage of low latency, low communication overhead and high uninterruptible connection. The DRAA protocol is a low-latency solution because each node independently allocates partial IP addresses and does not need to perform the duplicate addresses detection (DAD) during the node-join operation. Communication overhead is significantly lessened in that DRAA protocol uses the logical ring, thus utilizing fewer control messages solely by means of uni-cast messages to distribute address resources and to retrieve invalid addresses. Furthermore, if duplicate addresses are shown at network merging, the DRAA protocol checks the number of both TCP connections and of nodes to allow duplicate nodes to rejoin the smaller network so that lost connections are fast re-connected. To improve communication overhead and provide the evenness of address resources, the centralized ring-based address autoconfiguration (CRAA) protocol is discussed. The CRAA protocol reduces larger numbers of broadcast messages during network merging. The other contribution is that our CRAA protocol also has an even capability so that address resources can be evenly distributed in each node in networks; this accounts for the reason our solution is suitable for large-scale networks. Finally, the performance analysis illustrates performance achievements of RAA protocols. The simulation result shows that the DRAA protocol has the shortest latency, that the CRAA protocol has the capability to evenly distribute address resources and that both of DRAA and CRAA protocols are the good solutions which achieve low communication overhead and high uninterruptible connection.     

Random algorithms for scheduling multicast traffic in WDMbroadcast-and-select networks

We develop and analyze simple algorithms for scheduling multicast traffic in wavelength division multiplexing (WDM) broadcast-and-select networks with N nodes, W wavelengths, and a single receiver per node that can be tuned to any of the W wavelengths. Each message is addressed to κ randomly chosen nodes. Since optimal message scheduling in a WDM network is known to be very difficult, we study two simple scheduling schemes: in the first, a message is continuously retransmitted until it is received by all of its intended recipients; and in the second, a random delay is introduced between retransmissions of the same message. We develop a throughput analysis for both schemes using methods from discrete-time queueing systems and show that the algorithm with random delays between retransmissions results in higher throughput. We also consider a number of receiver algorithms for selecting among multiple simultaneous transmissions and show, through simulation, that an algorithm where the receiver selects the message with the least number of intended recipients performs better than a random selection algorithm. Finally, we show that channel utilization can be significantly increased with multiple receivers/node     

Energy-aware scheduling with probabilistic deadline constraints in wireless networks

In a shared-medium wireless network, an effective technique that allows for a tradeoff of message transmission time for energy savings is to transmit messages over multiple smaller hops as opposed to using the long direct source-destination hop. In this context, we address the problem of scheduling messages with probabilistic deadline constraints. Unlike most other works in this area, we consider the practical aspects of the erroneous channel condition and the receiver energy consumption while solving the scheduling problem. Our solution is three fold – first we prove that the problem is NP-hard. We then present an Integer Linear Program (ILP) formulation for the scheduling problem. Finally, we present efficient heuristic scheduling algorithms which minimize the energy consumption while providing the required guarantees. Our simulation studies show that the proposed heuristic algorithms achieve energy savings comparable to that obtained using the linear programming methodology under practical channel conditions.     

Scheduling variable-length messages in a single-hop multichannellocal lightwave network

The design of a medium access control scheme for a single-hop, wavelength-division-multiplexing-(WDM) multichannel local lightwave network poses two major difficulties: relatively large transmitter/receiver tuning overhead and large ratio of propagation delay to packet transmission time. Most schemes proposed so far have ignored the tuning overhead, and they can only schedule fixed-length packet transmissions. To overcome these two difficulties, the authors propose several scheduling algorithms which can reduce the negative impact of tuning overhead and schedule variable-length messages. A separate channel (control channel) is employed for transmission of control packets, and a distributed scheduling algorithm is invoked at each node every time it receives a control packet. By allowing the length of messages to be variable, a long message can be scheduled with a single control packet transmission, instead of fragmenting it into many fixed-length packets, thereby significantly reducing the overhead of control packet transmissions and improving the overall system performance. Three novel scheduling algorithms are proposed, varying in the amount of global information and processing time they need. Two approximate analytical models are formulated to study the effect of tuning time and the effect of having a limited number of data channels. Extensive simulations are conducted. Average message delays are compared for all of the algorithms     

Providing deterministic quality-of-service guarantees on WDM optical networks

A major challenge in the design of future generation high-speed networks is the provision of guaranteed quality-of-service (QoS) for a wide variety of multimedia applications. In this paper we investigate the problem of providing QoS guarantees to real-time variable length messages (e.g., IP packets) in wavelength division multiplexing (WDM) optical networks. In particular, we propose a systematic mechanism comprised of admission control, traffic regulation, and message scheduling that provide guaranteed performance service for real-time application streams made up of variable-length messages. We formulate an analytical model based on the theory of max-plus algebra to evaluate the deterministic bounded message delay in a WDM network environment using our proposed QoS guarantee mechanism to determine the "schedulability conditions" of multimedia application streams, We also conduct a series of discrete-event and trace-driven simulations to verify the accuracy of the analytical model. The simulation results demonstrate that the analytic delay bound we obtained for our WDM optical network is valid and accurate.     

Schedule-Based Cooperative Multi-agent Reinforcement Learning for Multi-channel Communication in Wireless Sensor Networks

Wireless sensor networks (WSNs) have become an important component in the Internet of things (IoT) field. In WSNs, multi-channel protocols have been developed to overcome some limitations related to the throughput and delivery rate which have become necessary for many IoT applications that require sufficient bandwidth to transmit a large amount of data. However, the requirement of frequent negotiation for channel assignment in distributed multi-channel protocols incurs an extra-large communication overhead which results in a reduction of the network lifetime. To deal with this requirement in an energy-efficient way is a challenging task. Hence, the Reinforcement Learning (RL) approach for channel assignment is used to overcome this problem. Nevertheless, the use of the RL approach requires a number of iterations to obtain the best solution which in turn creates a communication overhead and time-wasting. In this paper, a Self-schedule based Cooperative multi-agent Reinforcement Learning for Channel Assignment (SCRL CA) approach is proposed to improve the network lifetime and performance. The proposal addresses both regular traffic scheduling and assignment of the available orthogonal channels in an energy-efficient way. We solve the cooperation between the RL agents problem by using the self-schedule method to accelerate the RL iterations, reduce the communication overhead and balance the energy consumption in the route selection process. Therefore, two algorithms are proposed, the first one is for the Static channel assignment (SSCRL CA) while the second one is for the Dynamic channel assignment (DSCRL CA). The results of extensive simulation experiments show the effectiveness of our approach in improving the network lifetime and performance through the two algorithms.

     

Just-in-Time Scheduling for Multichannel EPONs

We investigate optical network unit (ONU) grant scheduling techniques for multichannel Ethernet passive optical networks (EPONs), such as wavelength division multiplexed (WDM) EPONs. We take a scheduling theoretic approach to solving the grant scheduling problem. We introduce a two-layer structure of the scheduling problem and investigate techniques to be used at both layers. We present an extensive ONU grant scheduling simulation study that provides: 1) insight into the nature of the ONU grant scheduling problem and 2) indication of which scheduling techniques are best for certain conditions. We find that the choice of scheduling framework has typically the largest impact on average queueing delay and achievable channel utilization. An offline scheduling framework is not work conserving and consequently wastes channel resources while waiting for all ONU REPORT messages before making access decisions. An online scheduling framework, although work conserving, does not provide the best performance since scheduling decisions are made with the information contained in a single ONU REPORT. We propose a novel online just-in-time (JIT) scheduling framework that is work conserving while increasing scheduling control by allowing the channel availability to drive the scheduling process. In online JIT, multiple ONU REPORTs can be considered together when making scheduling decisions, resulting in lower average queueing delay under certain conditions and a more effective service differentiation of ONUs.     

A high-performance message prioritization and scheduling protocol for WDM star networks

A high-performance Efficient Message Prioritization and Scheduling (EMPS) protocol, for intelligent message scheduling in Wavelength-Division Multiplexing (WDM) star networks is introduced. The performance of the well-known EATS and MSL schemes is noticeably degraded in practical networks with non-uniform destinations and non-negligible transceiver tuning latencies. Under these realistic conditions, it is common that two or more messages with the same destination have to be scheduled consecutively or at close times. In most cases, this brings about some performance penalty, owing to the delayed availability of the destination’s receiver for the second (and beyond) of the consecutive messages. As the frequency of such occurrences increases, the performance degradation of the existing schemes becomes more prominent. EMPS is proposed to deal with this problem. It simultaneously considers multiple messages from different transmitting nodes and gives priority to messages intended for the least used destinations each time. By balancing the offered load in this way, EMPS minimizes the probability of having to schedule two or more messages with the same destination consecutively or at close times. Additionally, by incorporating the Minimum Scheduling Latency algorithm for channel selection, the protocol also minimizes the actual performance penalty incurred, when scheduling of consecutive messages with the same destination cannot be avoided. Extensive simulations are carried out in order to study the performance of EMPS and compare it to other efficient schemes under various conditions. The simulation results show that the proposed protocol always brings about a significant performance improvement.     

Dynamic scheduling protocol for variable-sized messages in aWDM-based local network

In a single-hop star network based on wavelength division multiplexing (WDM), a protocol is needed for the transmitter and receiver to coordinate message transmission. This paper proposes a dynamic scheduling protocol which can efficiently support variable-sized messages, where a control channel is used to coordinate transmissions on data channels. The protocol does not require any global information. Therefore, it can operate independently of the change of the number of nodes, and any new node can join the network at any time without requiring network initialization. Moreover, with the protocol, one can avoid data channel and destination conflicts. The protocol is analyzed with a finite population model and the throughput-delay characteristics are investigated as performance measures     

Optimal Scheduling for Minimum Delay in Passive Star Coupled WDM Optical Networks

In this paper, a local optimization framework is proposed, which is able to include system constraints including channel availability, receiver availability and tuning overhead by linear mathematical formulations so that it is sufficient to obtain the optimal performance in terms of message delay. A mixed integer linear programming (MILP) based scheme for passive star coupled WDM optical networks is presented. Based on the new solution, the wavelength assignment and message sequence that guarantee the delivery of the given traffic request, while minimizing the average delay can be achieved. Moreover, the negative effect of the tuning overhead has been incorporated into the new algorithm, which has been ignored in most of the previous work. Numerical results obtained suggest that the proposed scheme is a promising approach for optimizing the network performance in terms of average message delay.     

Multi-hour design of computer backbone networks

This paper addresses the problem of designing wide area computer backbone networks that span many time zones. The problem of designing wide area computer backbone networks is commonly referred to as the Capacity and Flow Assignment (CFA) problem. The CFA problem involves the routing of messages and the assignment of communication line capacities at minimum cost subject to performance constraints. In this paper, a version of the CFA problem is addressed in which the assignment of communication line capacities is based on multi-hour traffic requirements. Multi-hour traffic requirements are used since networks that span many time zones have changing traffic patterns that exhibit non-coincidence of traffic over the hours of the day. Thus, low cost network designs can be obtained by exploiting this non-coincidence. A heuristic procedure is presented that takes advantage of this non-coincidence to provide low cost solutions. This heuristic procedure is applied to a variety of test problems and the solutions obtained are compared with lower bound solutions computed using a branch- and-bound procedure.     

Performance of Single-Hop WDM LANs Supporting Real-Time Services

Optical wavelength division multiplexing (WDM) local area networks are capable of fulfilling the enormous bandwidth demands of present and future applications. Up to now, the WDM LAN world is primarily dominated by the passive-star coupler (PSC) based architectures, for which many medium access control (MAC) protocols have been proposed. However, an arrayed waveguide grating multiplexer (AWGM)-based single-hop WDM network seems to be a very promising alternative. One of the most critical issues in designing next generation photonic LANs is the support of real-time services for applications with different time constraints. In this paper, different basic access protocols for the PSC as well as AWGM-based single-hop WDM LANs are considered and their performance in supporting real-time traffic is analyzed by means of extensive computer simulations. For evaluation of real-time performance, packet drop rates and deadline missing rates are taken as performance measures. Furthermore, new real-time message scheduling schemes are proposed which improve the performance of protocols accommodating mixed traffic. They can be differentiated between message scheduling at the source nodes transmit queues and scheduling based upon control information from a control channel. It is shown that both types of priority scheduling significantly improve the overall real-time performance.     

Minimum Interference Channel Assignment in Multiradio Wireless Mesh Networks

In this paper, we consider multi-hop wireless mesh networks, where each router node is equipped with multiple radio interfaces and multiple channels are available for communication. We address the problem of assigning channels to communication links in the network with the objective of minimizing overall network interference. Since the number of radios on any node can be less than the number of available channels, the channel assignment must obey the constraint that the number of different channels assigned to the links incident on any node is atmost the number of radio interfaces on that node. The above optimization problem is known to be NP-hard. We design centralized and distributed algorithms for the above channel assignment problem. To evaluate the quality of the solutions obtained by our algorithms, we develop a semidefinite program and a linear program formulation of our optimization problem to obtain lower bounds on overall network interference. Empirical evaluations on randomly generated network graphs show that our algorithms perform close to the above established lower bounds, with the difference diminishing rapidly with increase in number of radios. Also, ns-2 simulations as well as experimental studies on testbed demonstrate the performance potential of our channel assignment algorithms in 802.11-based multi-radio mesh networks.     

Channel Assignment for a Metro Hub Under Nonuniform Traffic

We consider a metro wavelength-division- multiplexing (WDM) network in which a metro hub connects multiple local networks to a backbone network. In many practical scenarios, the metro WDM network has nonuniform traffic. A metro hub recently studied in the literature can effectively transport nonuniform traffic via nonuniform channel assignment. To realize this feature, it is necessary to assign wavelength channels within the hub to fulfill the given channel requirements while avoiding wavelength conflict. In this letter, we formulate this wavelength assignment problem and propose an efficient method to solve it.      

保证航电波分复用网络实时性的虚拓扑设计

针对航空电子波分复用网络消息的实时性要求,对航空电子网络的结构进行了研究,分析了在该网络中造成消息延迟的主要因素为转发延迟。进而对航空电子网络建模,根据WDM网络的资源特性进行拓扑的约束,提出了基于综合考虑虚拓扑跳数以及消息的带宽保证为目标的线性规划算法,在此基础上给出了大型网络的一个启发式算法,采用该线性规划算法对NSFNet网络拓扑进行了仿真验证。仿真结果表明,综合考虑虚拓扑跳数和消息带宽能减少消息的延迟,保证了网络实时性。     

Algorithm for Scheduling Variable-Length Messages in WDM Networks

In this paper, we develop and analyze a simple algorithm for scheduling variable length messages in WDM networks with a passive star coupler. We base our schemes on a star topology with centralized control and use a scheduling algorithm similar to the process management in UNIX system. Every node and message have a scheduling priority associated with them. By comparing our algorithm with random select algorithm, we find that significant improvement in performance can be achieved with very little extra cost.     

Multi-wavelength all-optical networks with wavelengths outside theerbium-doped fiber amplifier bandwidth

Erbium-doped fiber amplifiers have become the dominating technology for signal amplification in all-optical networks. One constraint of EDFA's is that they have a much narrower bandwidth (≈25 nm) compared to the low-loss region (≈200 mn) of optical fiber. Instead of using only wavelengths within the bandwidth of EDFA's (i.e. the inband channels) for communication, we propose to include wavelengths outside the EDFA bandwidth (i.e. the outband channels) as well in order to increase the number of wavelengths and/or channel spacings that can be accommodated. Using outband wavelengths for sending messages presents a new constraint, namely that only if the power loss for transmitting a message is small enough can this message be transmitted on the outband wavelength. We develop wavelength-routing algorithms on arbitrary network topologies and wavelength assignments in hierarchical networks for sending messages subject to this constraint. We also analyze the SNR for inband/outband WDM signals