Soufiene Djahel

Yassine Hadjadj-Aoul

Renan Pincemin

CR-TMS: Connected Vehicles enabled Road Traffic Congestion Mitigation System using Virtual Road Capacity Inflation

Keywords: Connected vehicles, Smart cities, Road traffic congestion, Intelligent transportation system

Road traffic management experts are constantly striving to develop, implement and test a number of novel strategies to reduce traffic congestion impact on the economy, society and the environment. Despite their efforts, these strategies are still inefficient and a call for advanced multidisciplinary approaches is needed. We, therefore, introduce in this paper an original traffic congestion mitigation strategy inspired from a well-known technology in wireless communications, i.e. cognitive radio technology. Our strategy exploits Connected Vehicles technology along with the often under-utilized reserved lanes, such as bus and carpool lanes, to virtually inflate the road network capacity to ease traffic congestion situations. Two variants of our strategy have been evaluated using simulation and the obtained results are very promising in terms of the achieved reduction in average travel time for different vehicle classes including buses as well.

I. INTRODUCTION

The race towards building the first smart city with all the revolutionary features and services offered to its inhabitants is at its highest peak, especially in developed countries that have the financial resources and advanced technologies needed to achieve this goal. Indeed, smart cities are attractive because they advocate a futuristic vision of cities building sustainable ecosystems while promoting citizen welfare and economic growth. A smart city fosters the use of advanced ICT-driven solutions to smartly and efficiently monitor and manage its critical assets such as energy, water, and transportation infrastructure. Such an ambition can become a reality only with joint efforts from governmental, industrial, academic and social actors. Building smart cities, however, strongly depends on various enabling advanced technologies (e.g. intelligent sensing, 5G/B5G networks, Artificial Intelligence and connected vehicles, etc.) to support sustainable developments such as smart buildings, energy and smart mobility. Intelligent Transportation Systems (ITS) are considered as a main pillar of smart cities since the efficiency of several major services is reliant on their robustness and security level [START_REF] Djahel | A communications-oriented perspective on traffic management systems for smart cities: Challenges and innovative approaches[END_REF]. Transport experts foresee that ITS will be mainly comprised of automated or autonomous vehicles, cutting-edge transportation infrastructure in addition to innovative applications and services. Such infrastructure includes intelligent traffic light controllers, advanced traffic 1 Soufiene Djahel is with the Department of Computing and Mathematics, Manchester Metropolitan University, UK s.djahel@mmu.ac.uk 2 Yassine Hadjadj-Aoul is with Univ. Rennes, Inria, CNRS, IRISA, France yassine.hadjadj-aoul@irisa.fr 3 Renan Pincemin is with Telecom Physique Strasbourg, France renan.pincemin@outlook.fr monitoring equipment and sensing devices, etc. The main mission of ITS is to efficiently control and mitigate road traffic congestion problem that most cities suffer from.

The excessive traffic congestion in urban areas is mainly due to the increase in the vehicles' fleet, which in return causes accidents and worsens the congestion level on the already deteriorated road infrastructure. Traffic congestion has major impacts on the environment, the economy, and the population health, as stated in [START_REF] Boriboonsomsin K Barth | Real-world carbon dioxide impacts of traffic congestion[END_REF]. The last decade has witnessed an unprecedented revolution in developing advanced ICT driven solutions to mitigate the increasing road traffic congestion and alleviate its resulting impact on travelers' journey experience, road safety, air quality and economy. Such solutions include advanced vehicle routing and re-routing systems, such as [START_REF] Rezaei | Refocus+: Multi-layers real-time intelligent route guidance system with congestion detection and avoidance[END_REF] and [START_REF] De Souza | Safe and sound: Driver safetyaware vehicle re-routing based on spatiotemporal infor-mation[END_REF], traffic light signals optimization techniques [START_REF] Balta | A 3-stage fuzzydecision tree model for traffic signal optimization in urban city via a sdn based vanet architecture[END_REF], smarter and more efficient parking management systems [START_REF] Roman | Detecting on-street parking spaces in smart cities: Performance evaluation of fixed and mobile sensing systems[END_REF], bio-inspired computational intelligence [START_REF] Del Ser | Bioinspired computational intelligence and transportation systems: A long road ahead[END_REF] and machine learning [START_REF] Alsrehin | Intelligent transportation and control systems using data mining and machine learning techniques: A comprehensive study[END_REF] assisted transportation systems, etc. To complement these efforts, we propose an original traffic congestion mitigation system named CR-TMS (Cognitive Radio based Traffic Management System) that implements two traffic mitigation solutions: CRITIC (Cognitive Radio Inspired TraffIc Congestion) for which the preliminary evaluation results have been published in [9] and its extension CRITIC+. Compared to CRITIC, CRITIC+ takes into account the accumulated delay during the vehicle journey to compute a fair probability of access to the underutilized priority lanes. It also defines different classes of vehicles each has its own priority for promotion to the VIP class that grants access to priority lanes, and thus accelerates the vehicle progress towards its destination. Moreover, more accurate and fine grained evaluation is performed using more realistic parameters to accurately measure the impact of both CRITIC and CRITIC+ on the achieved average travel time.

The remainder of this paper is organized as follows. In Section II, we give a global view of the TMS architecture and its main components. Section III presents the main idea of CRITIC+ and describes the different classes of vehicles considered in this work. The simulation setting and experiments evaluation results are discussed in Section IV, followed by concluding remarks in Section V.

II. TRAFFIC MANAGEMENT SYSTEM: AN OVERVIEW

In the context of Smart Cities, the Traffic Management System (TMS) has a major role of smoothing traffic flow in order to avoid congestion. This latter has direct consequences on drivers, in terms of the experienced stress and increased travel delay, and leads to increased noise, energy consumption, and environmental pollution, which considerably degrades the quality of life of the city inhabitants.

The regulation of traffic flow necessarily passes by taking into account the environment and therefore the number of vehicles on the road, their directions, the topology of the road and the events impacting it such as the presence of roadworks, pedestrians and the occurrence of unpredictable incidents. This environment is typically monitored by deploying cameras or radars and different types of IoT sensors, in addition to Intelligent Traffic Lights (ITLs) equipped with communication capabilities that enable them to communicate with connected vehicles and thus, on the one hand, collect useful traffic data, and on the other hand notify them of any adjustments to road lanes usage rules or driving policies that require coordinated actions from them. These different probes regularly report traffic data back to the data collection and aggregation modules. Based on the data collected and processed, the Intelligent Traffic Light Controllers (ITLCs) can make the proper decisions to smooth traffic flow locally by sending recommended adjustments to the ITLs that they control. However, local traffic regulation, although useful, can sometimes create congestion at other levels, as reported in several studies [START_REF] Djahel | A communications-oriented perspective on traffic management systems for smart cities: Challenges and innovative approaches[END_REF]. In fact, the limited view of the overall traffic situation means that these local decisions can be wrong globally and lead to complex congestion situations that cannot be controlled easily.

Accordingly, we introduce, in the architecture shown in Figure 1, a global congestion evaluation engine that ensures that adjustments are made based on the acquisition of the overall view of traffic situations across the road network in a section of an urban area. Based on its global view of the traffic situation, this engine enables the optimization of local decisions made by ITLCs. The idea here is not to decide everything at the global congestion evaluation engine level, which would make the system very difficult to scale-up, but to allow ITLCs to adjust their decisions to make them better overall.

III. COGNITIVE RADIO-BASED TRAFFIC MANAGEMENT SYSTEM

In an attempt to virtually increase the road network capacity without building new roads that require substantial financial investment we propose to extend the existing TMSs by adding a new feature that enables opportunistic access to reserved lanes for a selected set of connected vehicles. The extended TMS is named CR-TMS (Cognitive Radio-based TMS) inspired from the cognitive radio technology principle widely adopted in wireless devices to increase their share of bandwidth, so that their transmission throughput improves, under certain constraints when their primary spectrum is overloaded. Similarly, CR-TMS is primarily intended, on the one hand, to relieve the congestion on regular (i.e., nonpriority) road lanes, allowing vehicles to move at higher speed and thus increasing the traffic throughput; and on the other hand, optimizing the usage of reserved (i.e., priority) Fig. 1: Traffic management system: from traffic data collection to congestion mitigation lanes capacity under certain conditions without slowing down their primary users (e.g., buses, carpooling vehicles, etc).

CR-TMS has similar architecture to the TMS shown in Figure 1 where the existing ICT-based road infrastructure is used for traffic data collection and ITLCs are leveraged to assess the traffic conditions on non-priority and priority lanes that they control. ITLCs are also responsible for creating access opportunities, for non-prioritized vehicles, to priority lanes if the access conditions are met. Such access conditions are evaluated either locally, by the ITLC, or at the global level by the GCEE, as shown in Figure 1. As a result of this evaluation CR-TMS decides about the optimal actions to be taken through triggering CRITIC or CRITIC+. In CR-TMS, we assume that the penetration rate of connected vehicles on the road is 100%, so the impact of human-driven cars is neglected in this work. CR-TMS intervention to reduce congestion is subject to the following conditions:

• Traffic using non-priority lanes is moving at a slow speed due to recurrent congestion or as a result of an unpredictable event. The speed reduction, compared to the speed limit of the lane, that makes this condition valid is expressed as follows.

FF speed -C speed FF speed ≥ threshold 1 (1)
where FF speed refers to the free flow speed and C speed denotes the current measured speed on this road lane. threshold 1 is a value dynamically set to reflect how fast CR-TMS should react to traffic congestion occurrence to anticipate any further consequences. • A priority lane is currently under-utilized because the number of priority vehicles using it is below the recommended usage rate by the traffic authority to ensure efficient usage of the road infrastructure. The usage rate that makes this condition valid is expressed as follows.

|RU rate -CU rate | RU rate ≥ threshold 2 (2)
Such that CU rate defines the current usage rate observed on the priority lane while RU rate represents the recommended usage rate of such lane by the priority vehicles.

Once the above conditions are met, CR-TMS will trigger CRITIC+ whose main operations are summarized in the Algorithm 1. Please note that CRITIC+ defines three classes of vehicles as explained below.

• Prioritized vehicles (P-vehicle): such as buses and carpool vehicles, any vehicle in this class will, by default, use any Priority Lane (PL) in its route to the destination.

A. The promotion process: from NP-vehicle to VIP-vehicle

Once the conditions for the promotion are met, as shown in the above algorithm and Equations 1 and 2, CRITIC+ measures the hosting capacity of the priority lane (see Equation 3) and the required reduction of the load on the Non-Priority Lanes (see Equation 4) to determine the number of vehicles to be promoted (see Equation 5). Where Length(PL) refers to the length of the priority lane, AVG VL is the average length of a vehicle, FFS NPL represents the Free Flow Speed of the congested non-priority lane while AVG Speed (NPL) denotes its current average speed. It is worth to mention as well that the Safety Distance is computed based on the maximum speed allowed in the priority lane.

The selection of vehicles to be promoted to the VIPvehicle class is made based on three criteria:

• Their power source (i.e. electricity, hybrid, and fossil fuel), where an electric vehicle has a higher chance of promotion as it contributes more to transport sustainability. Moreover, the aim of this work is to support the emergence of electric vehicles use due to its positive impact on the environment. • The remaining travel distance to reach the destination.

Here, vehicles with longer trips have higher chances of being selected for promotion. • The accumulated waiting time, at intersections and due to traffic congestion, since the start of the vehicle trip. Vehicles with longer waiting times are favorite for promotion. For each non-prioritized vehicle i, normalized values of the above three criteria along with their corresponding weight values are used to compute its probability, as shown in Equation 6, for promotion to the VIP-vehicle class.

Pr(i) = (W power × Power value (i)) + (W trip × Trip value (i)) +(W waiting-time × Waiting-time value (i)) (6)
Such that Power value is set to different values, in ] 0,1] , for electric, hybrid and fossil fuel vehicles. Trip value (i) is a normalized value representing the remaining travel distance for the vehicle i trip and calculated according to Equation 7. Waiting-time value (i) is a normalized value that denotes the accumulated waiting time of the vehicle i and is computed according to Equation 8.

Trip value (i) = Trip(i) Maximum trip (7)
Where Trip(i) denotes the remaining distance to the destination for the vehicle i, while Maximum trip represents the maximum value of this distance among all the vehicles using this congested non-priority lane.

Waiting-time value (i) =

Waiting-time(i) Maximum waiting-time [START_REF] Alsrehin | Intelligent transportation and control systems using data mining and machine learning techniques: A comprehensive study[END_REF] Such that Waiting-time(i) represents the accumulated waiting time of the vehicle i during its trip so far while Maximum waiting-time refers to the maximum experienced accumulated delay among all the vehicles using this congested non-priority lane. Now, the ITLC selects the non-priority vehicles with the highest Pr(i) values (i.e. the top Subset size vehicles) and notify them that they have been promoted to the class VIPvehicle and are now able to move to the under-utilized priority lane(s). Notice that for safety and traffic efficiency purposes, the ITLC may choose to notify a lower number of vehicles than the selected Subset size vehicles, mainly based on their current positions within each lane.

IV. PERFORMANCE EVALUATION AND ANALYSIS

To evaluate the performance of CRITIC and CRITIC+, we conducted experiments using the microscopic traffic simulator SUMO and TraCI packages. We used 7×7 Grid network topology consisting of 2×2 lanes and set the distance between every two consecutive junctions to 250 m, similar to Manhattan road network in New York City. Two scenarios were tested, in the first one, the most outer lane on 25% of the network edges was used as a priority lane (i.e., a lane reserved for buses) while in the second scenario 50% of the edges have such a reserved lane. As an example, if we examine an area of 2km 2 around the Grand Central Terminal in Manhattan we can find that 23% of edges have a reserved bus lane. The experiments were run 30 times with a varying seed value at each run. Three categories of vehicles are considered in the simulation: buses, private vehicles, and electric vehicles. The details of the simulation setting are summarized in Table I. The weight values for the three selection criteria, used in equation 6, are set to 1/3 each in our simulation but different values could be also used if traffic authorities want to give more importance to one specific criterion for example. During the simulation, nonprioritized vehicles with promotion probability greater than or equal to 0.6 are promoted to the VIP-vehicle class until the Subset size is reached or there is no further non-prioritized vehicle that meets the promotion conditions. The results plotted in Figures 2 and3 are measured for three use cases. In the baseline scenario, non-priority vehicles are not permitted to use the priority lanes so both CRITIC and CRITIC+ are disabled. In CRITIC, all non-prioritized vehicles moving on a congested non-priority lane are allowed to use the under-utilized priority lane if no bus is detected on it. Finally, in CRITIC+, only selected non-prioritized vehicles based on the promotion probability computed in Equation 6are allowed to move to a priority lane if it is under-utilized.

Figure 2 depicts the achieved Average Travel Time (ATT) for different vehicle classes under varying percentages of buses inserted in the traffic flow. We can see that both CRITIC and CRITIC+ lead to a lower ATT compared to the baseline with the most important reduction achieved when the percentage of buses is 12%. We notice as well that CRITIC+ has lower ATT than CRITIC in many cases. This shows the advantage of selecting a subset of vehicles to use the priority lane, instead of allowing all vehicles, as the latter might sometimes just shift the congestion to the priority lane instead of using it to virtually increase the road capacity and relieve the congestion situation. Moreover, a large number of lane change maneuvers leads to additional delays due to the coordination needed between connected vehicles for increased safety [10]. These results highlight that not only electric and private vehicles benefit from CRITIC and CRITIC+ but also the buses, which are the prioritized vehicles that use the priority lane reserved for them. The reason behind that is the fact that buses will not use priority lanes during their whole trip but only when they exist on a road segment, in this case, 25% of road segments have a priority lane, and as CRITIC and CRITIC+ alleviate the congestion on non-priority lanes this will benefit the buses as well when they use them.

Figure 3 highlights the relation between the percentage of available bus lanes in the road network and the efficiency of CRITIC and CRITIC+ in reducing the ATT. Similar to the previous results, CRITIC+ outperforms CRITIC in most of the cases. Moreover, the benefit of both CRITIC and CRITIC+ is more important when the percentage of bus lanes is higher (i.e., 50%) because in this latter case traffic congestion is worse since the capacity of non-priority lanes is lower compared to the scenario of 25% of bus lanes. From this, we conclude that our proposed CR-TMS performs better when the percentage of bus lanes (or reserved lanes in general) in the road network is higher.

V. CONCLUSION

In this paper, we have tackled the problem of optimizing roads' traffic within the context of smart cities. We propose a strategy, inspired from cognitive wireless networks, to improve urban road lanes management. More specifically, our original idea in this work consists in improving the use of non-priority lanes by partially off-loading traffic onto priority lanes, without impacting the flow of traffic on the latter. The developed policy has clearly reduced the effects of congestion by reducing travel times for non-prioritized vehicles. An unexpected benefit of such a strategy has been to improve travel time even for prioritized vehicles such as buses. As a future work, we plan to develop a probabilistic model and advanced control strategy to achieve optimal

3 ) 4 )

 34 PL Hosting-capacity = Length(PL) + Safety Distance AVG VL + Safety Distance (NPL Load-reduction = ( FFS NPL -AVG Speed (NPL) FFS NPL ) ×#Vehicles (Subset size = min(PL Hosting-capacity , NPL Load-reduction ) (5)

Fig. 2 :

 2 Fig. 2: Impact of the percentage of buses on the achieved ATT in CRITIC and CRITIC+: a scenario of 7*7 grid map with 25% of bus lanes

  • Non-Prioritized Vehicles (NP-vehicle): any regular vehicle that does not belong to the above class. By default, any vehicle in this class will use the Non-Priority Lanes (NPL) during its route to the destination.• VIP-vehicle: this class is defined dynamically where a number of vehicles belonging to NP-vehicle class are selected to temporarily use the available priority lanes.

	Algorithm 1: The main operations of CRITIC+
	Result: The set of VIP-vehicles
	Input: Road network edges;
	IoT sensors reading;
	ITL collected data;
	for Each road segment do
	if PL exists then
	if At least one P-vehicle is using PL then
	Revoke PL access to VIP-vehicle class;
	Reinitialize VIP-vehicle class;
	else
	-Determine the hosting capacity of PL;
	-Determine the required load reduction in
	congested NPLs;
	-Determine the size of the subset of
	vehicles to be promoted from NP-vehicle
	class to VIP-vehicle class;
	-Compute the selection probability of each
	NP-vehicle currently using NPLs;
	-Select the vehicles to be promoted and
	update VIP-vehicle class;
	-Notify the promoted vehicles;
	end
	else
	Check the next road segment;
	end
	end

TABLE I :

 I Simulation setting


Ali Hodroj
email: ali.hodroj1@net.usj.edu.lb

Marc Ibrahim Saint

Yassine Hadjadj
email: yassine.hadjadj-aoul@irisa.fr

Parallel Streaming for a Multi-homed Dash client

Keywords:

Nowadays, multimedia streaming traffic reaches 71 % from the mobile data traffic over the world and most of the multimedia services use Dynamic adaptive streaming over HTTP (DASH) to adjust video delivery to the dynamic network environment and achieve higher user Quality of Experience (QoE) levels. Moreover, 90 % of the video traffic is consumed by smart devices equipped with multiple network interfaces (Wifi, 3G, and 4G) known as multi-homed devices. In this paper, we propose a new DASH-parallel streaming solution, which exploits the diversity of access network connections to improve video quality over DASH protocol. Experimental Results show that our proposed approach improves the perceived QoE in different network conditions, without requiring further energy expenditure.

I. INTRODUCTION

According to the Cisco Visual Networking Index, the demand for video traffic is increasing and exceeds 78% of the total mobile data traffic by 2021 [START_REF]Cisco. Cisco visual networking index forecast and methodology[END_REF]. Most of the video services are today based on adaptive streaming techniques that allow a video to be played based on the end user's network conditions. Therefore, the quality of the video and the audio streams are automatically adjusted accordingly, enhancing the user's experience [START_REF] Vlaović | Evaluation of adaptive bitrate selection algorithms for mpeg dash[END_REF].

Dynamic adaptive streaming over HTTP (DASH), which is becoming the dominant protocol for video delivery, works by dividing the media content into a sequence of small HTTPbased file segments, each chunk consists of a short interval of playback time of the media content [START_REF] Sodagar | The mpeg-dash standard for multimedia streaming over the internet[END_REF]. In DASH, video content is represented by two elements: The media Presentation Description (MPD) file and the video/audio Segments [START_REF] Casey | Mpeg-dash-based framework for improving end-user video experience in heterogeneous multi-network wireless environments[END_REF]. The MPD is an XML manifest file that identifies multiple components and the location of all alternative streams. After analyzing the MPD, the client requests and download an appropriate segment, which guarantees smooth playback of the video file and enhances the QoS and performance since the client knows its capabilities (i.e. the received throughput, the delay, the terminal's potential -screen resolution -) [START_REF]Dynamic adaptive streaming over http (dash) -part 6: Dash with server push and websockets[END_REF] [START_REF] Mueller | Dynamic adaptive streaming over http/2.0[END_REF] [START_REF] Zhou | Towards simple and smooth rate adaption for vbr video in dash[END_REF].

From a traffic perspective, smartphones will continue to dominate mobile traffic (up to 93% by 2022). As smartphones are multi-homed devices [START_REF]Samsung galaxy s5 download booster[END_REF], usually equipped with multiple radio interfaces (3G, 4G, and WiFi), this potentially allows the device to connect to multiple networks at the same time.

This emerging diversity of access networks could be used to improve the perceived video quality. In this paper, we study the use case of a multi-homed DASH client that aims to watch a video content replicated in many DASH servers, as shown in Figure 1. For this purpose, a parallel streaming mechanism over DASH is proposed to enhance the QoE for multi-homed clients. Our solution permits the client to request a segment simultaneously using both available connections, to provide a kind of bandwidth aggregation mechanism that maximizes the available resources (connections), which allow improving the received video-rate without any quality degradation due to the variation of the network's conditions on both connections. Additionally, it provides the following features:

• More robustness using the content replication to ensure high data availability, as a user can use multiple sources to prevent any quality degradation due to congestion at the server side. • Parallel streaming over DASH, as a Dash client can request a segment using multiple connections simultaneously.

• Smart downloading mechanism. Indeed, the main question when using multi-homing is how to ensure that the way of splitting the data among multiple connections is efficient? our downloader response about this question is described in Section 3. • An energy-saving mechanism, as using parallel streaming increase power consumption and without any quality improvement in some cases.

The remainder of the paper is organized as follows. Sections II describes the latest solution proposed in Multi-homing over DASH. Section III presents a description of our proposed solution. we evaluate our Parallel Streaming algorithm over DASH, in section IV. Finally, a conclusion and future research ideas are provided in Section V.

II. RELATED WORK

This section represents a summarized survey about the related works in multi-homing and muti-paths solutions for video streaming. Min Xing formulate the video streaming process as Markov decision process (MDP) and propose a multi-link rate adaption (MLRA) mechanism using multihoming features [START_REF] Xing | Rate adaptation strategy for video streaming over multiple wireless access networks[END_REF]. At each set of segments request (considered as time step), we use MDP to optimize the Quality of Experience of video content by evaluate the current situation and reward function of available states.The objective of this approach is to improve the QoE while reducing the cost of using multiple connections. MLRA algorithm selects the next segment based on the current buffer level and the estimated available bandwidth. It takes into consideration the calculated reward function of each decision (using only a wifi link or both links or smoothing).

Using the same concept of MPD problem formulation, [START_REF] Xing | A real-time adaptive algorithm for video streaming over multiple wireless access networks[END_REF] proposes a real-time adaptive search (RTRA) algorithm to improve video performances. The results show that RTRA achieves higher quality in different bandwidths scenarios (rapid and slow-changing) and reduce startup delay, which leads to user stop watching the video in most cases, up to half and better smoothness.

A cross-layer approach was proposed in [START_REF] Corbillon | Cross-layer scheduler for video streaming over mptcp[END_REF] based on an interaction between the application and transport layer which lead to decrease video distortion and improve video quality. This approach consists of using Multi-Path Transmission Control Protocol (MPTCP) as the transport layer with some additional features considered to add feedback that indicates the path to be selected by MPTCP for the next packet. Also, an adaptive content-aware scheduler is used at the application layer to estimate the playback deadline and thus determine which video segment and when is given for transmission. The objective of this solution is to maximize the received data on time, to prevent the receiving buffer from being fully occupied by many packets waiting for the delayed packet (head-ofline blocking). Also using the content awareness, it ignores the transmission of segments that will miss their playback deadline when checking the Picture Order Counts (POC) of each segment and gives more priority to the segments which their deadline period is near to expire. Another cross-layer approach was proposed in [START_REF] Ojanperä | Network-assisted multipath dash using the distributed decision engine[END_REF] using DASH and MPTCP. A Distributed Decision Engine (DDE) was proposed as a network monitor systems responsible for providing the accurate network information's on each interface. This network information's are used in the Dash bit rate adaption, then MPTCP is responsible for sending the data over multiple paths. The results show that more accurate information's lead to better bit rate adaption and improve video performance.

Similar to before, the MP-DASH framework [START_REF] Han | Mp-dash: Adaptive video streaming over preference-aware multipath[END_REF] was proposed to extend MPTCP for dealing with multiple network interfaces over DASH protocol. Two modules were integrated for this purpose the scheduler and video adapter. The scheduler is based on user input preferences about network paths and throughput aggregation between paths. It consists of two parts: decision function that determines how to manage paths and enforcement function that operates the decisions. The video adapter is implemented to enhance the Dash adaptive bit-rate mechanism by exchanging the useful information (throughput, segment size and deadline time) between the scheduler and player. The main idea from this work is to meet user quality requirements with the Wifi link alone and use the cellular data (3G) when wifi cannot deliver data before the deadline period. The result, in comparison to default MPTCP, shows a valued decrease in cellular usage up to 99% and 85% in energy consumption. A new cross-layer approach between transport and network layer was proposed in [START_REF] Nam | Towards dynamic mptcp path control using sdn[END_REF].In this work, MPTCP is used with a path controller module based on Software Defined Networking (SDN) platform. Network information's about different paths is monitored using the SDN controller and periodically transmitted to SDN clients permitting to evaluate and characterize the available paths (remove paths that lead to out-of-order delivered packets due to low throughput). This solution was implemented over DASH and results show better QoE is achieved with this path controller module on MPTCP.

The author in [START_REF] Chowrikoppalu | Multipath Adaptive Video Streaming over Multipath TCP[END_REF] modified the DASH protocol to support multihoming features. This modification consists of adding a scheduler, adaptation algorithm and bandwidth estimator on the DASH plugin. The bandwidth estimator measures the available bandwidth on each interface by sniffing packets and estimates the bandwidth in the future based on present and previous measurements. The adaption algorithm uses the estimated bandwidth for rate adaptation for each requested segment. The scheduler is responsible for scheduling requests for segments.

A video delivery utilizing over multiple paths was proposed in [START_REF] Houzé | Applicative-layer multipath for low-latency adaptive live streaming[END_REF] to achieve low latency in DASH video streaming. Two adapted mechanisms are proposed in this approach. The first determines the best byte-range size of each divided segment over multiple paths, in order to receive them before the deadline. Thus, the larger byte ranges are transmitted over better paths which decrease the delay and solve the HOL problem. The second one is responsible for selecting a suitable representation with the highest quality that can arrive on time.

A network selection mechanism based on the Multi-Armed bandit algorithm was proposed in [START_REF] Hodroj | Enhancing dynamic adaptive streaming over http for multi-homed users using a multi-armed bandit algorithm[END_REF] for a DASH multihomed client. The proposed solution permit the user to select the suitable interface at each decision time, which enhance the average perceived video quality. Also the default adaptive bitrate rule of DASH require some modifications to deal with different network conditions over different paths, which was validated in the results of several experiments with and without this modification.

III. PROPOSED SOLUTION

In this paper, we propose a Parallel Streaming solution over multi-homed DASH (PS-DASH) for video streaming as an application solution that does not require any kernel modifications at the server or the client sides.

Our solution benefits are:

• Channel diversity: Using multiple connections allows the user switching to an alternate path in case of failure or congestion in the current path. Moreover, it permits the user to use both connections simultaneously, a kind of bandwidth aggregation, to achieve higher video quality. Many challenges may occur when adding multi-path features to video transmission starting from Head Of Line blocking (HOL) problem, network heterogeneity, out-oforders packets, and end-to-end delay. Our solution deals with such challenges simply and smartly, as described in the next section. • Source diversity: The increased demand, for highquality video services, was observed in the CISCO forecast. This may lead to an overload at the server-side, which results in increasing the end-to-end latency and quality degradation at the client-side. To deal with such a problem, we take the advantages of Content Delivery Networks (CDN) where the content is replicated at multiple servers' locations and permit the client to watch the video from several sources. Thus, each client is able to download the video content from various sources based on the expected high quality that can be achieved from each server [START_REF] Adhikari | Unreeling netflix: Understanding and improving multicdn movie delivery[END_REF]. • Quality enhancement: Using parallel streaming and source diversity permit the client to increase its network speed. One of the main challenges in parallel streaming is the respect of the packets' order in video transmission to avoid packets' jitter, unnecessary waiting time in the buffer causing buffer overflow or HOL problems. Moreover, in adaptive streaming, the main advantage is to choose the corresponding video quality based on network conditions. Our proposed solution keeps allowing the adaptive bitrate algorithm to more accurate bitrate adaptive decisions due to a more accurate measurement of network conditions over multiple connections. • Energy savings: Our solution takes into consideration the use of parallel streaming when it leads to enhanced quality, which reduces energy consumption. Our solution keeps monitoring the network conditions and checks the available bit-rate of video content. Thus, if one connection is fast enough to meet the higher available video quality, no need to use a second connection.

A. Model

• Q = {q j } j=1..N Q is the set of available N Q video qualities. • I = {I i } i=1..N I : the set of available N I network interfaces. Only two interfaces are considered in this work. • P s : the segment video duration.

• t: the time step for the PS-DASH algorithm. The duration of the time step is equal to n × P s , where n is the fixed number of segments to download in a time step. • S(t): the segment size at time t, which is equal to

N I i=1 s i (t)
, where s i (t) is the amount of data from segment s download through interface i at time t.

• b(t): the amount of buffered video data at time t.

• T (t): the time required to download the segment S(t) at time t. • w(t): the throughput to download segment S(t) at time t, which is equal S(t) T (t) equal to

N I i=1 w i (t)
, where w i (t) is the throughput of interface i at time t.

B. PS-DASH Design

Parallel streaming over the Dash algorithm is based on using multiple connections simultaneously to download each requested chunk from the client in a fastest way.

Many studies have been developed to determine how we divide different segments or split a segment among multiple connections. The splitting mechanism was a challenge because it leads to quality degradation when network conditions are wrongly predicted or estimated. For this purpose, we use a simple way, which doesn't need any network estimation and results in a fastest download. The idea here is to start downloading the current segment from the beginning of the segment, via the first connection, while downloading it from the end on the other interface (see Fig. 2). The download stops when the entire segment has been downloaded, as described by the MPD file. The main concept of DASH is the adaptive bitrate algorithm that permits the user to switch between the available video rates according to its network conditions and other information that affects the video performances (e.g. like the buffer level). Using multi-homing affects these rules and leads in some cases to quality degradation. Indeed, the decision on the choice of the segment's quality can be based on the conditions of another interface, with a very different status. Our smart segment downloader doesn't suffer from this problem as it is working in intra-segment, which means that it doesn't affect the measurements of the available bitrate (ABR). Thus, it is based on the whole segment not a part of the segment.

In order to estimate the network conditions, we propose to use the average throughput w i to download the next segment.

w i (t + 1) = αw i (t) + (1 -α)w i (t) (1)
Where α represents a weighting factor giving more or less weight to the current measured throughput. Also, another use case of switching to single connection streaming instead of parallel is when the current receiver buffer is full, thus, no need for a faster transmission. w 0 (t + 1) = αw 0 (t) + (1 -α)w 0 (t)

7:

w 1 (t + 1) = αw 1 (t) + (1 -α)w 1 (t) 8:
if (Qmax > max w0,w1 ) AND (b(t)!= FULL) then i = 1

14:

[S], w 0 , w 1 = REQUEST(n, Q, i)

15: t = t + 1 16: function REQUEST(n, Q, i) 17:
if i == 0 then As mentioned in Algorithm 1, the Dash client starts downloading n segments through both interfaces, using the function Request(n, q init , 2) where q init is the default quality request based on DASH ABR, using the Smart Downloader mechanism. After receiving the n segments, the function measures the throughput of each interface i, which is equal to the amount of data S i downloaded through this interface divided by the downloading time. Then, the algorithm estimates the throughput of each interface based on the exponential weighted moving average, as shown in Eq. ( 1). Before requesting a new set of segments, the algorithm checks if the maximum available quality (already known from the MPD file) can be reached through one of the two interfaces alone, and keep track of the current buffer level. If one of these two conditions is satisfied, the algorithm decides to request the next set of segments using single transmission and through the highest available throughout. Otherwise, it uses the parallel transmission mechanism with the same procedures until the end of the video.

IV. PERFORMANCE EVALUATION

We implemented a test-bed (see Figure 3) to evaluate our proposed solution in different scenarios, taking into consideration different network connections characteristics. Our testbed consists of a DASH client with multiple interfaces, each interface is connected to a DASH server. We use the Won-derShaper application on each server to control the network characteristics and emulate the required variations [START_REF] Wondershaper | [END_REF]. We focus, in our measurements, on the following parameters to evaluate our solution:

1) Average video bitrate: the average of received video quality. 2) Buffering time: the time of empty buffer occurrences waiting to receive the segments for streaming. 3) Gain parameter: the quality enhancement resulting from using parallel streaming. 4) Energy Saver: prevent using parallel streaming, which causes more energy consumption, when there is no possible quality enhancement. The scenario consists of a standard DASH Client that watches the video content. Each scenario is repeated with different network throughput's in three types of network variations: without, smooth and rough variation. the smooth variation refer to speed variation with ±20% each 2 minutes, while the rough variation refer to speed variation with ±40% each 1 minutes.

The result, in Figure 4, shows how the different network throughput affect the average received video quality in DASH. Better quality is achieved in fast throughput with stable network conditions, and it decreases according to throughput decreases.

B. PS-DASH Measurement

we divide our experiment of evaluation into two parts. In Part 1, we study quality enhancement as a metric of evaluation, while in part 2, we study the cost of using parallel streaming in terms of energy consumption.

1) Quality Evaluation: In these experiments (Figure 6), we refer to Multi-homed DASH client that watches the same video content using both connections simultaneously with a combination of different network throughput. Then each scenario is repeated with the three types of network characteristics (without, smooth and rough intra-variation of network characteristics). To evaluate our algorithm, 192 scenarios were run: Each scenario consists of a DASH Multi-homed client watching the video content, while fixing the speed of the first connection and changing the speed of the second connection using all speed values, from the speed list. The 64 scenarios, resulting from the combination of the speed list, are repeated with the three types of network variations. We calculate the Enhancement E (Equation 2) resulting from comparing the average video bitrate Q 2 of our algorithm to that one measured from using the highest throughout alone Q 1 in a single transmission.

E = Q 2 -Q 1 Q 2 (2)
Figure 7 shows the Cumulative Distributed Function (CDF) of the average enhancement calculated from these sets of experiments, when comparing our algorithm using the Parallel Streaming over DASH to the standard Dash (single transmission) using the highest connection.The result shows quality enhancement between 10% to 95% in 80% from the scenarios, while 10% from the 192 scenarios were subject to quality degradation in comparison to single transmission. Besides, we can notice the absence of any empty buffer occurrences when using the PS-DASH algorithm. 2) Energy Consumption Evaluation: In these measurements, we refer to a Multi-homed client that watch different video content,each video content has different bitrate representations. Each scenario is repeated two or three times using different speeds (as Show in Table I). The objective of these measurements is to check the network utilization in different scenarios, to ensure that our algorithm doesn't use the parallel streaming when the maximum quality is reached through the speed of the highest single connection. The Parallel Streaming usage is mentioned on top of each result. One can observe that the parallel streaming usage is decreasing in all cases when the highest available quality can be achieved through one network connection. For example, in the first video content, we have two available qualities, and we make two measurements that refer to two different sets of throughput. The result shows that parallel streaming usage is decreased from 70% to 18% while the highest video quality (1013 kbps) can be achieved through the second connection throughput (2Mbps) alone. In all scenarios, we observe the same conclusion with a different variation of decreasing. In this paper, we propose a Parallel Streaming algorithm for multi-homed DASH clients. We showed that the PS-DASH algorithm improves the average video bitrate while reduces rebuffering time. Furthermore, our algorithm takes into consideration the potential wastage of energy when using parallel streaming. We are planning to upgrade our algorithm to take into consideration the current buffer status related to the rate of decoding to reduce energy consumption. Moreover, we are planning to study the network capabilities of multiple connections, comparing to available video quality bitrate, not just checking if the highest qualities can be archived using single streaming.

Video

Fig. 1 .

 1 Fig. 1. Multihoming Infrastructure

Fig. 2 .

 2 Fig. 2. Smart Downloader

Algorithm 1

 1 PS-DASH Algorithm 1: q init = DEFAULT 2: t = 0 3: [S], w 0 , w 1 = REQUEST(n, q init , 2) n is the number of requested segments 4: Push [S] to DASH player 5: while t < C c do while video not finished 6:

  Download segments via both interfaces23: return [S], w 0 , w 1 -

Fig. 3 .

 3 Fig. 3. Experiment Lab Testbed Setup

Fig. 4 .Fig. 5 .

 45 Fig. 4. Video quality variation in function of Throughput variations

Fig. 6 .

 6 Fig. 6. PS-DASH Experiments

Fig. 7 .

 7 Fig. 7. Average Bitrate Enhancement of MP-DASH Algorithm

Figure 8

 8 Figure 8 represents the average video bitrate received for different video contents using different sets of network speeds.The Parallel Streaming usage is mentioned on top of each result. One can observe that the parallel streaming usage is decreasing in all cases when the highest available quality can be achieved through one network connection. For example, in the first video content, we have two available qualities, and we make two measurements that refer to two different sets of throughput. The result shows that parallel streaming usage is decreased from 70% to 18% while the highest video quality (1013 kbps) can be achieved through the second connection throughput (2Mbps) alone. In all scenarios, we observe the same conclusion with a different variation of decreasing.

Fig. 8 .

 8 Fig. 8. Parallel Streaming usage in function on speed variations for different video contents


G Rubino

Introduction

• Among the multiples faces of AI (methods, applications, tools, ...) we will focus today on

Subjective testing (cont.)

• The result is a table M where component M h,σ is the value given by human h to sequence σ. • A statistical procedure is then followed to filter these results in order to remove outliers. • At the end, if the set of surviving observers is S, the quality of sequence σ, its MOS (Mean Opinion Score) value is

MOS(σ) = 1 |S| h∈S M h,σ .
• The procedure is surprisingly robust: with the same set of sequences but a different panel, the same subjective test gives results extremely close to the first one: if µ σ and µ σ are the MOS values of sequence σ in both panels, the number σ µ σ -µ σ 2 is pretty "small".

-Measuring Perceptual Quality

Subjective testing (cont.)

• For each type of media, there are norms specifying how to perform the corresponding subjective test. A reference here is the production of the ITU (International Telecommunication Union). • For instance, some norms ask users to watch video sequences potentially degraded by some noisy effect, and rate them from 1 to 5 according to the following table :   MOS score description 5 degradation imperceptible 4 degradation perceptible but not annoying 3 degradation slightly annoying 2 degradation annoying 1 degradation very annoying

• The norms specify also other constraints concerning details such as the lengths of the sequences, the timing of the subjective testing session, its own length, the experimental conditions (e.g. monitor contrast or viewing distance in case of video), the suggested panel's size, etc. • In video, most subjective tests norms belong to the following classes: • The panel must also be built following some rules (similar to those followed to make opinion polls). The idea is to build a representative sample of the users of the considered application/service, or of the subfamily of users we are interested in. • Obviously, subjective testing is costly, takes time, and by construction is not usable for real time perceived quality assessment. • Comment: one of the goals of my team at Inria is to use quality assessment techniques for monitoring and for control purposes. So, only methods that work automatically qualify.

Objective testing

• Objective testing means evaluating the perceived quality automatically, without using any panel of users. • To give an example, consider video sequences. Some objective testing methods (coming from the coding area) are based on the PNSR (Peak Signal To Noise Ratio) of two images A and B:

• for instance, assume the two images are composed of M rows and N columns of 8-bits pixels (monochrome case). • The MSE (Mean Squared Error) between the two images is

MSE(A, B) = 1 MN M i=1 N j=1 A i,j -B i,j 2 ∈ [0..255 2 ].
• The PSNR between the two images is defined only if they are different (MSE = 0) and its value (in dB) is

PSNR dB (A, B) = 10 log 10 255 2 MSE(A, B)
.

Objective testing (cont.)

• We can classify objective testing in three categories:

• full reference methods: the original sequence is needed;

• partial reference methods: some values related to the original sequence are needed; • no reference methods: the original sequence is not needed.

• Some objective testing techniques are said to be signal-based : we must explore the content of the sequence to assess its quality. • Other methods are said to be parametric: the quality is evaluated based on some parameters related to the system (source parameters and/or network parameters).

Objective testing (cont.)

• The main advantage of objective methods is that they by-pass the use of panels of observers. • In VoIP there are some important examples such as the E-model, and others. • However, in general objective metrics often correlate poorly with subjective ones ("the truth").

Example in VoIP

Bad correlation between an objective metric and subjective tests in Voice over IP.

Resuming

• Consider any kind of application or service consisting basically in transporting audio and/or video signals over the Internet. • The media can be sent one-way (e.g., a video streaming service) or two-ways (e.g., an IP-telephony application). • For many reasons (compression techniques used, congestion in the network leading to delays, and/or to losses, external perturbation agents such as interferences in some networking technologies, etc.) transmission can suffer from content degradation. • Perceptual quality (PQ) refers to the (subjective) perception (the view, the feeling) the user has on the quality of this media transmission system, on the quality of what she receives, on the impact of the degradations due to the transmission over the network.

• Two main characteristics:

• It is, by definition, a subjective concept.

• It lacks a formal definition.

• Somehow perceptual quality is at the heart of the designer's goals for these systems, it is her ultimate target, complemented by some other aspects of system's properties (e.g. security). • It is measured daily using panels of humans, following specific norms.

The area is called subjective testing , and the resulting PQ numerical value (we say a MOS value, for Mean Opinion Score) is very robust. • At our team in INRIA, we decided to look for automatic and real time measuring techniques.

• There are objective testing methods, avoiding using panels:

• some come from coding, and compare the received signal to the original one; we say that they are methods with reference (they need to access the original signal); • others consist of analyzing the received signal only, looking for impairments; they are no reference methods.

• Both have strong limitations:

• accuracy, the most important one,

• and lack of real time capabilities.

• Comment: new objective techniques have been developed where accuracy has been improved. More on this later. PSQA: Pseudo Subjective Quality Assessment

Outline

• In the Dionysos team we promote our solution called PSQA to all the initial problems and many more, for all types of media considered, and for both one-way and two-ways communications. • PSQA is a metric with no reference, automatic, (so far, "optimally") accurate, and it works in real time if necessary or useful. • PSQA is network-dependent and application-dependent.

• It is a parametric approach (a "black-box" approach), mapping QoS parameters and source-based parameters into perceptual quality (into a MOS value).

PSQA (cont.)

• The mapping is based on statistical learning tools and it is built in such a way that it has nice mathematical properties. We can use it in many ways, for instance,

• for sensitivity analysis: which is the dominating factor having an impact on quality? where is it significantly dominating? • for inverse problems: which values of the considered factors lead to a high enough MOS value? • etc.

• More specifically, so far PSQA functions are a particular class of rational functions coming from the Random Neural Network (or G-network) area.

PSQA (cont.) How PSQA works

• First of all, we select (i) measurable QoS metrics characterizing the state of the network (logically speaking, instantaneous measures), and assumed, a priori, to have an impact on the Perceptual Quality, (ii) and metrics related to the channel or to the source, again, expected to have impact on the PQ.

• Example in video: (i) the instantaneous packet loss rate LR, (ii) the Bit Rate BR and the Frame Rate FR. • Example in VoIP: (i) the instantaneous packet loss rate LR, the average size of a burst of loss packets MLBS , (ii) the Bit Rate BR and the Offset of the FEC (Forward Error Correction) OFEC .

• Let x = (x 1 , . . . , x n ) denote the vector whose components are the n chosen metrics. We call it configuration.

• Configurations live in some product space S 1 × • • • × S n .
• Our postulate: PQ depends only on x (when "things go well") and not on signal content. • We select a few short signals (following standards) representative of the application or service target, σ 1 , . . . , σ K . • We build a pretty small set of K configurations (K = 100, 200, ...) by a mix of random sampling and quasi-Monte Carlo (or weak discrepancy sequences). Call them γ 1 , . . . , γ K . • Last, we build a platform allowing to send signals σ i through a simulated or deployed network where we can simultaneously control all components of the configurations.

• Then we send different original σ i using the platform, when the configuration is γ j using one configuration at a time, and obtain a possibly degraded sequence σ j . We show it to a panel of humans and we obtain its PQs Q j . • We thus obtain a set of K sequences, with variable but known PQ (MOS values) coming from subjective testing sessions, and for each, we know which configuration was used to obtain it. • Then, we use a RNN (a G-network), of the classical feedforward type with 3 layers, to learn the mapping from configurations to PQ (a mapping from QoS×"channel state" to MOS values). Data: the M pairs γ j , Q j . • In the example of video, we obtain a function ν(LR, BR, FR). In the VoIP example, we obtain a function ν(LR, MLBS , BR, OFEC ).

Training results for PSQA (video example) • There are many other activation functions used in practice:

(
z = tanh(u -b), z = 1(u ≥ b), RELU, ...
A Random Neural Network (RNN) is a set of interconnected RNs. The connections are weighted by nonnegative reals denoted w + i,j and w - i,j for the weights of the connection from i to j arriving at the positive and negative ports respectively.

+ - z 1 0 x neuron 1 + - z 2 neuron 2 for instance, u 2 = z 1 w + 1,2 v 2 = z 1 w - 1,2 + - z 3 neuron 3
Jonctions at input ports are additive:

+ - neuron 3 + - neuron 1 + - neuron 2 u 3 = z 1 w + 1,3 + z 2 w + 2,3 v 3 = z 1 w - 1,3 + z 2 w - 2,3
recall that weights w * i,j are nonnegative

Feed Forward RNNs

• In this case (for instance, a simple multi-layer architecture), the output coming out of the last layer is a rational function of the inputs. • This allows many nice mathematical processing of the trained networks.

Random Neural Networks implement rational functions

• Assume the negative ports of input neurons aren't used. Assume a single output neuron, so, a scalar network output. • Call x i the signal arriving at the positive port of input neuron i. Then, we can explicitly write the network output as a function of the inputs.

z o = h∈H i∈I x i r i w + i,h r h + i∈I x i r i w - i,h w + h,o r o + h∈H i∈I x i r i w + i,h r h + i∈I x i r i w - i,h w - h,o
.

• This shows that the output is a rational function of the input. This allows many treatments. Also, for learning, costs (errors) are rational functions of weights, again, allowing some specific mathematical treatments. Main issue

Outline

• With PSQA, we know how to measure the PQ very accurately and in real time, and as you saw, to measure PQ we actually need to measure QoS metrics and channel metrics, the input variables of our PSQA function.

• So, to predict PQ, we need to predict the values of those input variables. • Some of them will be rather static, and their values come for free.

Others need measures. The hardest part of this prediction problems is to predict future values of a time series (for instance, traffic intensity, or loss rates).

Time series prediction

• Predicting the future of a time series is an old topic in statistics. The applications are uncountable (economy, finance, engineering, meteorology, climate, ...). • With the explosion of AI techniques (and the associated results), AI entered the game, and using learning methods have provided new efficient prediction tools. • We will describe here the subarea of Machine Learning where we worked, and then, our own tools there. • A couple of facts related to the topic:

• Recurrent neural networks are good for memorizing information, so, well-behaving for time series predictions. • Recurrent neural networks are harder to train than Feed Forward ones.

Reservoir Computing (RC)

• RC neural networks are an attempt to develop models that uses the potential for memorization of recurrent neural networks without the difficulties in the training process of these networks.

• They appeared at the beginning of the 2000s.

• The two most popular RC models are The origin of the terminology:

• In the LSM literature, the reservoir is often referred to as the liquid term used in neurosciences for the brain. • In the ESN community, the dynamic reservoir and its states are termed echoes of its input history. • It is an intuitive metaphor of the excited states as ripples on the surface of a pool of water.

Echo State Networks (ESNs)

We focus on the ESN implementation of the RC idea.

• An untrained recurrent part called reservoir.

• A memory-less supervised learning tool called readout.

Three-layered recurrent neural networks:

• Input layer

• Hidden layer

• Output layer a ∈ R Na x ∈ R Nx ŷ ∈ R Ny
The learning process is restricted to the output weights (readout).

ESN properties

Some aspects of the ESN model:

• The iterative computation of x(t) can be unstable due to the recurrences. • The stability behavior is controlled by the spectral radius of the weights in the reservoir. • In addition, the spectral radius has some impact on the memory capability of the model. • The Echo State Property (ESP): an ESN has the ESP if for t 1, x(t) basically depends on the input history only (and not on how the reservoir was built).

ESP

The Echo State Property

• Even though the trajectories of the reservoir states are random initialized, the model should be independent of the initial network trajectories in the long term. • The network needs to have some type of fading memory with respect of the initial conditions and initial dynamics. • These characteristics are established in the ESP.

• The ESP establishes that the trajectories of reservoir states depend only of the input driven network, they don't depend on the initial conditions of the network. • If the spectral radius of the reservoir's weights is < 1, we have the ESP (sufficient condition); a necessary condition is to have it ≤ 1.

Some practical issues

Stability of the recurrences in an ESN model:

• A simple procedure for creating an ESN is to randomly initialize the reservoir weight matrix and then to scale it using a factor α. • The selection of the scaling factor is important for the ESP.

• Previous sufficient condition can be very conservative; it can also produce a negative impact on the long memory capacity of the reservoir. • In practice, the reservoir weights are scaled such that α < than the inverse of the spectral radius. • Concerning the activation function, no strong constraints.

Tuning ESNs

Main adjustable parameters of a RC model: Our work in predicting time series for PSQA 2.0

• As Random Neural Networks behaved so well for our PQ-measuring applications, we decided to keep close also for predicting PQ. • We took one of the most promising ideas in ML applied to the problem, and worked on its adaptation in the Random Neural Network world. • The result is described in next slides.

• The input space in then projected into a new "larger" space.

• We compute a linear regression from the projected space to the output space. • Thus, the network output

ŷ (t) = (ŷ 1 (t), . . . , ŷN b (t)) is computed for any m ∈ [1..N b ]: y m (t) = w out m,0 + Na+Nx i=1+Na w out m,i ρ i (t). (2)
• The output weights can be computed using, for instance, a Regression. Remark: we can replace this simple structure by, for instance, a classical feedforward 3-level RNN (to be explored). • Practical aspects of our uses of RNN in learning:

"Evaluating Users' Satisfaction in Packet Networks Using Random Neural Networks", G. Rubino, P. Tirilly and M. Varela, Springer-Verlag Lecture Notes in Computer Science, no. 4132, 2006.

• An example of using RNNs in combinatorial optimization:

"A GRASP algorithm with RNN-based local search for designing a WAN access network, H. Cancela, F. Robledo and G. Rubino, Electronic Notes in Discrete Mathematics 18 (1), 59-65, December 2004.

• An example of application of PSQA:

•

  Single Stimulus (SS): only the distorted signal is shown to the panel, • Double Stimulus Continuous Quality Scale (DSCQS): both the original and distorted sequences are shown simultaneously • Double Stimulus Impairment Scale (DSIS): first the original sequence and then the distorted one are shown.

•

  Results are not surprising.) Let us see a "classic artificial neuron" as a parametric real function of a real variable. u z; for instance, z = 1 1 + e -u+b bias b • Consider b as a parameter of the function implemented by the neuron.

Figure : Figure :

 :: Figure: NARMA validation data set. The reservoir was randomly initialized and it had 80 units.

•

  Figure shows a projection of the sequence of reservoir states using PCA. The spectral radius of the reservoir matrix (in the graphics was mentioned as ρ, is the usual notation). This is an important global parameter of the model. It is used for controlling the memory capacity of the model, and it controls the stability of the recurrent dynamics. The graphic illustrates the different behavior of the ESN model according to the spectral radius, and also compares with the reservoir states of the ESQN. There are four collections of points that correspond to the projection of the reservoir state of different ESN models. The collection of black dots corresponds to the projection of the ESQN reservoir state to 2D. The weights of the ESQN were randomly fixed in [0, 0.1]. similar than previous one: In this case the reservoir of the ESQN has weights in [0, 0.25]. The graphic shows how the ESQN dynamics depend in the initial values assigned to the ESQN reservoir. It is visible that the dynamics are very different for values in [0, 0.1] and values in [0, 0.25]. Probably, the interval also depends on the number of neurons. As a consequence, how to fix the reservoir can affect the results. The procedure for fixing the initial weights of the ESQN reservoir have been only empirical in our case, we are trying to figure out a general automatic procedure. Maths behind our main application: "Quantifying the Quality of Audio and Video Transmissions over the Internet: The PSQA Approach", G. Rubino, in Design and Operations of Communication Networks: A Review of Wired and Wireless Modelling and Management Challenges, edited by J. Barria, Imperial College Press, 2005.

•

  Details in Basterrech and G. Rubino, "Echo State Queueing Networks: a combination of Reservoir Computing and Random Neural Networks", Prob. in the Eng. and Informational Sciences, 2017.

  Note: Henon Map as input data. ESN has 50 fully connected reservoir neurons and spectral radius (ρ) equal to 0.5.

			Echo State Queueing Network Echo State Queueing Network Comments
							Input sequence -Henon map Input sequence -Henon map
		1 1
	0.8 0.8 0.08 Note about the previous picture: Projection of reservoir state in 2D
		0.4 0.6 0.4 0.6 0.06 Input value Input value			rho=0.1 rho=0.5 rho=0.7 rho=0.99
		0.2 0.2 0.04			ESQN
	Neuron state value PCA component 2	5050 0 0 0.02 0.04 0.06 0.08 5050 0 1 2 3 4 5 x 10 -3 -0.04 Neuron state value -0.02 0 0.02	5055 5055	5060 5060	5065 5065	5070 Example of classic ESN dynamics 5075 5080 time 5070 5075 5080 time Example of ESQN dynamics	5085 5085	5090 5090	5095 5095	5100 neuron 5 neuron 15 neuron 30 neuron 50 5100 neuron neuron neuron neuron
		-0.06
		5050 -0.02 5050 0	5055 5055	5060 5060	5065 5065	5070 5070	5075 5075	5080 5080	5085 5085	5090 5090	5095 5095	5100 5100
								time time
		-0.08	0	0.02	0.04	0.06	0.08	0.1	0.12	0.14	0.16	0.18	0.2
							PCA component 1
	Note: Henon Map as input data. ESQN has 50 fully connected reservoir
	neurons with weights randomly fixed between [0, 0.1].

  "Controlling Multimedia QoS in the Future Home Network Using the PSQA Metric", J.-M. Bonnin, G. Rubino and M. Varela, in The Computer Journal, 49(2):137-155, 2006.• On the design of a P2P streaming network based on PSQA:"A robust P2P streaming architecture and its application to a high quality live-video service", H. Cancela, F. Robledo Amoza, P. Rodríguez-Bocca, G.Rubino and A. Sabiguero, in Electronic Notes in Discrete Mathematics 30: 219-224, 2008, plus another paper with a demo, "Automatic Quality of Experience Measuring on Video Delivering Networks", D. De Vera, P. Rodríguez-Bocca and G. Rubino, in SIGMETRICS Performance Evaluation Review, Vol. 36, Issue 2, associated with a demonstration at Sigmetrics'08 awarded with the Best Demonstration Prize.

Coimbatore, Feb. 21, 2020

-Measuring Perceptual Quality Subjective testing (cont.)

-Measuring Perceptual Quality

-Measuring Perceptual QualityProblems with PSNR approach...Same amount of noise in the grass

-The PSQA technology

-Our ESQN tool

-Final remarks and some conclusions

Subjective testing

• Subjective testing is the standard way of measuring perceived quality.

• A panel of appropriately chosen human observers is built, and a set of media sequences is shown to the panel members. • Following specific rules (absolute rating, comparisons...) the observers say how they perceive the quality of the sequences. • In case of interactive applications, observers can work by pairs, or in some cases, interact with a robot.

Problems with PSNR approach

Noise in the sky

Example in audio

Bad correlation between an objective metric and subjective tests in audio.

Validation results for PSQA (video example)

Very good accuracy of the tool:

Comparing RNN with ANN Under exactly the same (reasonable) conditions and with the same data (an example, there are many other ones):

Random Neurons

• A Random Neuron is a parametric positive real function of two real positive variables (we also say "ports"), one called the "positive port", the other one being the "negative port".

• The real r > 0, the rate of the neuron, is a parameter of the function.

• There are several variants of this model. In the main and original one, we must use z = min(u/(r + v ), 1). • Inventor: E. Gelenbe, Imperial College, in the late 80s.

• Observe that there is nothing random here. The name comes from the origin of the model (queueing theory). Echo State Queueing Networks: applying the RC idea to a G-network.

• Three sets of neurons, recurrent topology "in the middle".

• Input at time t, a(t) = (a 1 (t), . . . , a Na (t)):

Weights notation as classical NNs: u sending spikes to v is denoted by w On some of the parameters of ESQN:

Summary about the ESQN tool

• The impact of the reservoir size is similar to the impact of the number of neurons in a classical network. • The spectral radius behave in ESQNs as in ESNs: close to 1 is fine for problems with long range data correlation needing long memory capabilities, and close to 0 it is ok in the opposite case. • The impact of the sparsity of the reservoir is unclear. Typical recommendations for ESNs are about 15%-20% and we found that this seems also appropriate for ESQNs.

Concluding remarks

• The analysis of the RC approach is still fairly open, and the situation is similar for the ESQN model. • There are several important parameters to adjust: reservoir's size, reservoir's connections, reservoir's weights, then, spectral radius of the reservoir matrix. • ESNs and ESQNs work very well in many cases for time series modeling.

• This good behavior is not well understood.

• Both ESNs and ESQNs require some expertise for setting their parameters.

• We would like to find conditions for the initialization of the weights in order of guaranteeing good predictions (something such as ESP for ESNs). • A good (optimal?) structure for the readout is to be found. • Analysis of several theoretical questions around Reservoir Computing with our ESQN model (mainly around convergence, stability, etc.). • In PSQA, the labels come from subjective tests (that is, from panel of human subjects). We have a project whose goal is the elimination of the (main) use of those panels. This leads to

• Big Data problems, coming from the extensive use of automatic but less performant tools to provide quality assessments of huge amounts of sequences, • and then, to the exploration of the use of specific deep architectures for the learning phase (not necessarily related to RNNs). • An example of extension of the initial RNN tool:

Outline

"Echo State Queueing Networks: a combination of Reservoir Computing and Random Neural Networks", S. Basterrech and G. Rubino, in Probability in the Engineering and Informational Sciences, Vol. 31, No. 4, pp. 1-16, 2017.


The problem addressed here is the derivation of closed forms of the solution to linear systems of difference or differential equations which have constant coefficients, a "simple" or "regular" structure, but that have, in some cases, infinite size.

These types of systems appear in many areas, in particular in the transient analysis of Markovian queueing models.

We developed a methodology based on the concept of duality in Markov chains as proposed by Sigmund and developed by Anderson 1 , and used it on basic queueing models (M/M/1, M/M/1/H, M/M/1 and M/M/1/H with failures or catastrophes, etc.).

1 Continuous-Time Markov Chains, W. J. Anderson, published by Springer in 1991 (out of press).

Duality concepts

Back to general remarks

Outline

Interest and extension

The goal of having closed forms is, obviously, to get insight into the solution to the considered models.

This was the motivation with those stochastic models. Transient analysis is necessary today, for instance in telecommunications, to know what happens on short finite time intervals, and not only in equilibrium.

Later, we extended this duality idea to arbitrary differential systems, not necessarily coming from stochastic processes. This paper describes new work in this direction.

Exponential-duals

Key result

Let M be an arbitrary square matrix. Using previous properties, e Mt = e Mt .

In words, the exponential-dual of the exponential of Mt is the exponential of the power-dual of M times t.

This result explains how the evaluation of the power-dual appears when we work on matrix exponentials.

In this short presentation with skipped some technical results that are needed to prove previous theorem.

Using the dual to analyze Markovian queues

From a given Markov process X to analyze, living on the nonnegative integers, (i) we build a new one, its Anderson's dual as we call it, X * (if it exists, which is not always the case).

The transformation is linear (the generators are linearly related), and its main property is that the solutions to both systems are linearly related, and in the two directions: X → X * and X * → X .

Then, the idea is to (ii) find the transient distribution of X * , in general using Uniformization, to move to discrete time and thus analyzing the transient distribution of a Markov chain Y * (typically counting paths by means of lattice path combinatorics tools).

To finish, (iii) we come back at X using the inverse dual (linear) transformation.

In cases with some regularity in the structure, this can produce closed-forms solutions, and it can also work when the dimension of the initial problem is infinite (e.g. for the M/M/1 queue). Back to general remarks

Outline

Comments

This procedure is useful when X * is easier to analyze, in a way or another.

As we see, there is an initial continuous time phase, then a discrete time part process, where a transient distribution is needed.

In some cases, we have a discrete time problem for which we look for transients from the beginning (instead of ODEs we have then difference equations).

In this talk we will briefly describe a general approach where transients in continuous time (algebraically speaking, matrix exponentials) or in discrete time (matrix powers) are needed. The former are built using the latter.

To simplify the discussion, we only present here in the finite case. The power-dual of a matrix

Talk's content

Let M be a square matrix (of reals, of complex numbers, ...) with dimension n. Let us index it on {0, 1, . . . , n -1}. The power-dual of M is a new matrix that we denote here M, with dimension n + 1 and indexed on {0, 1, . . . , n -1, n}, defined as follows:

M i,j =            n-1 k=i M j,k - n-1 k=i M j-1,k if j ≤ n -1, 1 - n-1 k=0 M n-1,k when j = n, where M -1,k = 0. Example, dimension 2: M = a b c d ; M =   a + b c + d -(a + b) 1 -(c + d) b d -b 1 -d 0 0 1   Back to general remarks Power-duals
Example, dimension 3:

M =   1 -1 2 2 0 -2 1 -3 3   ; M =     2 -2 1 0 1 -3 2 1 2 -4 5 -2 0 0 0 1    
A stochastic matrix:

P =   2/5 0 3/5 1/6 1/2 1/3 0 1/4 3/4   ; P =     1 0 0 0 3/5 7/30 1/6 0 3/5 -4/15 5/12 1/4 0 0 0 1     ;
as we see, in this case the power-dual is not a stochastic matrix; Another stochastic matrix:

P = 2/5 3/5 1/6 5/6 ; P =   1 0 0 3/5 1/15 1/3 0 0 1   ;
here, the power-dual is also a stochastic matrix. Back to general remarks

Power-duals

Some properties

If M is the power-dual of matrix M, then the sum of the elements of any row of M is 1, and the last row is composed of 0s except for its last element = 1.

Inversion Lemma: for 0 ≤ i, j ≤ n -1, we have

M i,j = i k=0 M j,k - i k=0 M j+1,k .
Central result: For any two square matrices A and B with the same dimension, we have AB = B A.

Corollary: for any square matrix M and any nonnegative integer k,

M k = M k .
In words, the power-dual of the kth power of M is the kth power of M's power-dual.

Duality concepts Back to general remarks

Exponential-duals

The exponential-dual of a matrix

Let M be a square matrix (of reals, of complex numbers, ...) with dimension n. Let us index it on {0, 1, . . . , n -1}.

The exponential-dual of M is a new matrix that we denote M, with dimension n + 1 and indexed on {0, 1, . . . , n -1, n}, defined as follows:

M i,j = n-1 k=i M j,k - n-1 k=i M j-1,k , where M -1,k = 0. Example, dimension 2: M = a b c d ; M =   a + b c + d -(a + b) -(c + d) b d -b -d 0 0 0  
We can observe that if we denote by W a square matrix with the same dimension as M, composed of 0s except the last column composed of 1s, then we have M = M -W .

Introduction Duality concepts

Back to general remarks

Exponential-duals

Example, dimension 3:

M =   1 2 3 -1 2 -3 0 2 -2   ; M =     6 -8 2 0 5 -6 1 0 3 -6 1 2 0 0 0 0    
An infinitesimal generator:

M = -λ λ µ -µ ; M =   0 0 0 λ -(λ + µ) µ 0 0 0   ;
as we see, the exponential-dual is also an infinitesimal generator; Another infinitesimal generator:

M =   -3 1 2 6 -7 1 1 2 -3   ; M =     0 0 0 0 3 -9 5 1 2 -1 -4 3 0 0 0 0     ;
here, the exponential-dual is not an infinitesimal generator.

Talk's content

Introduction Outline

Duality concepts

Power-duals Exponential-duals Back to general remarks Take H = 4, to shorten the slides. Denote Λ = λ + µ + γ. We have

A =       -λ λ 0 0 0 µ + γ -Λ λ 0 0 γ µ -Λ λ 0 γ 0 µ -Λ λ γ 0 0 µ -(µ + γ)      
If we move to discrete time using Uniformization, the computation of e At translates into that of evaluating U k where using the notation p = λ/Λ, q = µ/Λ, r = γ/Λ,

U = I -A/Λ is U =       q + r p 0 0 0 q + r 0 p 0 0 r q 0 p 0 r 0 q 0 p r 0 0 q p      
The powers of U are hard to obtain in closed-form here.

If we use the exponential-dual (plus Uniformization), we must compute the powers of

P =        
1 0 0 0 0 0 p 0 q 0 0 r 0 p 0 q 0 r 0 0 p 0 q r 0 0 0 p q + r r 0 0 0 0 0 1

       
Due to those '1' at the corners, the use of lattice path combinatorics is much easier here than with matrix U of previous slide. That's an example of situation where we can develop the process until its end.

The infinite case can also be solved in the same way.

The formal solution of the ODEs (Chapman-Kolmogorov equations) is given below, using the notation ρ = λ/µ, for the case of the queue starting empty at time 0 (the general case is similar while more complex): In the formula, π j denotes p j (∞) (steady-state), easy to evaluate symbolically.

p j (t) = π j - 2µρ

Some properties

If M is the exponential-dual of matrix M, then the sum of the elements of any row of M is 0, and the last row of M is composed of 0s.

Inversion Lemma: 0 ≤ i, j ≤ n -1, we have

Important result: for any two square matrices A and B with the same dimension, we have AB = B A.

Corollary: for any square matrix M and any nonnegative integer k,

In words, the exponential-dual of the kth power of M is the kth power of M's exponential-dual.

Duality concepts

Back to general remarks

Exponential-duals

Let A and B be two square matrices with the same dimension, and α be a scalar. We have Other general properties:

If P is a stochastic matrix, then the first row of P is (1 0 0 . . . 0 ). Recall that P need not be stochastic.

If A is an infinitesimal generator, then the first row of A is (0 0 0 . . . 0 ). Recall that A need not be an infinitesimal generator.

Connection with the dual of a Markov process as defined by Sigmund in 1976 and developed in Anderson's book: if A is the infinitesimal generator of Markov process X and if A is also an infinitesimal generator, the associated Markov process X * is the dual of X .

Duality concepts Back to general remarks

Overview

This work generalizes the use of duality in the theory of Markov processes as proposed by Sigmund (see Anderson's book). The dual doesn't always exist.

In previous work we proposed to define what we call here exponential-dual, adopting a purely algebraic approach, when we realized that the stochastic framework was not necessary for the interest we had in the concept. Many proofs needed to be rewritten.

Here, we decompose explicitly the cases of discrete time and continuous time, and exhibit their connections, making the construction more complete and consistent.

On dual's existence (Markov processes)

This concerns the historical origin of this work, in the stochastic processes area.

For instance, consider an homogeneous "ring" illustrated here for 3 states:

Whatever the size of the ring and the value of λ, the associated Markov process has no dual (for those familiar with duality in Markov processes, the problem is the monotonicity condition impossible to satisfy here).

Consider now the general Markov process with 3 states:

Here, the dual exists iff

Duality concepts Back to general remarks

Zoomming on an example

Consider here the M/M/1/H queue plus "catastrophes" (or failures) as shown in the following Markovian graph:


Outline

Introduction

Initial technique

Improvements

Main assumption

Transitions are either slow or fast. Two examples:

• models of highly dependable systems:

• failures → slow transitions,

• repairs → fast transitions;

• queueing models in light traffic environments:

• arrivals → slow transitions, • departures → fast transitions.

• We want to evaluate

R = E(r X∞ ) = x r x π x ,
where X ∞ is a stationary version of the ergodic stochastic process X , r x ≥ 0 is the reward associated with state x, π is the distribution of X ∞ .

Intuition

• Because of previous setting, X spends "most of its life" in a "small" part of the state space, "close to 0", "around the left side of the space". • Idea: try to keep this "left side" of the state space and replace the rest by "a few states", obtaining some new model such that evaluating the target on it we will get a good approximation of R. • Actually, this leads to several such auxiliary small models, that allow to build some lower and upper bounds of R. • To denote lower bounds of some real w we will use the notation [w ] lb , and [w ] ub for an upper bound.

On the target

• Examples: if the system is a queue in equilibrium, or some subset of a queueing network, R can be the mean number of customers in it, or the probability that it has more than N customers; in a dependability model, R can be the asymptotic availability, or some mean cost, etc. • The bounding approach described here can handle many large (sometimes infinite) Markov models with very general structures. • It can solve for models where matrix geometric techniques cannot be applied.

• We assume that we cannot compute x r x π x (too costly, for instance, because computing π x for all x is too costly itself) but that upper and lower bounds of the rewards are available.

Example 1 • Previous picture shows a queueing network seen as a generalization of the Machine Repair Model. It has two classes of customers, and a Coxian server, making that, in the general case, the network is not a product-form one • Putting, for instance, 80 type 1 units and 120 type 2, a 6-phases Cox distribution for the repair time of type-1 machines, and a 5-phases one for type 2 ones, we obtain a model with 4,344,921 states. • Assume that the system works iff at least 79 type 1 units and 115 type 2 ones are alive.

• Previous picture shows a queueing network seen as a generalization of the Machine Repair Model. It has two classes of customers, and a Coxian server, making that, in the general case, the network is not a product-form one • Putting, for instance, 80 type 1 units and 120 type 2, a 6-phases Cox distribution for the repair time of type-1 machines, and a 5-phases one for type 2 ones, we obtain a model with 4,344,921 states. • Assume that the system works iff at least 79 type 1 units and 115 type 2 ones are alive. • This M/E 2 /1-> ./E 2 /1 tandem has an infinite state space and no analytic solution. • For instance, if we set λ = 0.18 and ν = 1 we obtain a mean number of customers = 1 with error less than 0.01, solving a linear system having around 200 elements.

Example 4

total capacity H3 lambda mu1 mu2 mu3

total capacity H2

• Here, servers 1 and 2 block after service if next node is full, and when a position is freed they instantaneously send the served (and blocked) customer.

• Again, we have an infinite state space and no analytic solution.

• Using λ = 0.2, µ 1 = 0.7, µ 2 = 1.5, µ 3 = 0.2, H 1 = 18, H 2 = 10, we obtain the metric E(N ∞ ) with error < 10 -10 solving a linear system with size 3839.

Outline Introduction Initial technique

Improvements

• That is, the state space of X is partitioned into (G , G c ).

• In X (j) we force all transitions from G c to G to enter G by the same state j. The stationary distribution of X (j) ix π (j) . • G , G c , j ∈ G are arbitrary.

Starting result:

• There exists {β j } j∈G , β j ≥ 0, j∈G β j = 1, s.t.

π = j∈G β j π (j) .
• Proved by Courtois & Semal. We improved the result slightly in previous joint work with S. Mahévas, then again recently when preparing this paper. • In this presentation, we will give a more explicit statement.

Consequences

• Let R (j) = E(r X (j) ∞ ) = x r x π (j) x . Then, R = j∈G β j R (j) . • =⇒ min j∈G R (j) ≤ R ≤ max j∈G R (j)
• Bounding technique (proposed by Muntz, De Souza e Silva and Goyal, see next slide): use some computable lower and upper bounds of previous bounds:

min j∈G R (j) lb ≤ R ≤ max j∈G R (j) ub .
Sources for the initial model Nice use of the results of Courtois and Semal to obtain an operational procedure to compute tight bounds. Some assumptions are strong.

• Mahévas and Rubino, Bound computation of dependability and performability measures, IEEE Trans. Comp. 50 (5), 2001

Some improvements to previous ideas, with much weaker applicability conditions, plus integrating the case of infinite state spaces, and opening the path to the new recents advances.

Pseudo-aggregation

• For instance, consider

G c = C 1 + C 2 (partition of G c into two classes).
• The pseudo-aggregation of X (called "exact aggregation" by Courtois), denoted X here, obtained by collapsing C 1 (resp. C 2 ) into state c 1 (resp. c 2 ), is a new Markov chain that

• has state space G + {c 1 , c 2 } (that is, |G | + 2 states), • with, for instance, rate(c 1 , c 2 ) = x∈C1 π x y ∈C2 Q xy x∈C1 π x , etc.
• Observe that X is Markov by construction. Also observe that to build X we need π.

Main property

• Let π be the stationary distribution of X .

• We have:

π c 1 = x∈C 1 π x , π c 2 = x∈C 2 π x ,
and for all x ∈ G , π x = π x .

Who is G ?

• Consider, for instance, that X models a queueing network.

• Let ν(x) = # of customers in some subnetwork of the model when the state, in equilibrium, is x. We want to know, for instance, the mean number of customers in that subnetwork, in equilibrium, that is,

E(ν(X ∞ )). • Define C L = {x : ν(x) = L}. • We set G = L<K C L , G c = L≥K C L .
• Assume (only to simplify the presentation) that jumps are only possible inside the classes, or from C L to C L-1 and to C L+1 .

• In a dependability context, X can represent the configuration of some complex system having many components belonging to M different types, subject to failures and repairs. • A state could be a vector x = x 1 , . . . , x M where x m is the number of failed components of type m. • Transitions of X correspond to failures of some components, possibly repairs, to some configuration changes in the system, etc. • We have a function Φ defined on the state space of X , where Φ(x) = 1( sys. is up when in state x ). The goal could be, for instance, to bound the system's asymptotic availability:

P( sys. up in equilibrium ) = P(Φ(X ) = 1) = E Φ(X ) . • If ν(x)
is the number of failed components when the state is x, a class of states could be C L = {x : ν(x) = L}.

Next step

• Once K chosen, we set G = C 0 + C 1 + • • • + C K -1
(we denote by '+' the union of disjoint sets). • Let us denote by X the pseudo-aggregation of X with respect to the partition G + {c K , c K +1 , . . .}, where class C L is collapsed into a single state c L . • If we consider the same transformation as before, forcing the transitions in X that go from c K into G to enter by an arbitrary chosen state j ∈ G (necessarily j ∈ C K -1 ), it is easy to see that X (j) ≡ X (j) .

Pseudo-aggregations

c K c K +1 • • • c L • • • λ K µ K +1 λ K +1 µ K +2 λ L-1 µ L+1 λ L µ L+2 G X Pseudo-aggregations c K c K +1 • • • c L • • • λ K µ K +1 λ K +1 µ K +2 λ L-1 µ L+1 λ L µ L+2 G X c K c K +1 • • • c L • • • λ K µ K +1 λ K +1 µ K +2 λ L-1 µ L+1 λ L µ L+2 j G X (j) ≡ X (j) (easy to prove)
The last picture can be simplified as follows:

c K c K +1 • • • c L • • • λ K µ K +1 λ K +1 µ K +2 λ L-1 µ L+1 λ L µ L+2 j µ (j) K G X (j) ≡ X (j)
We have µ

(j) K = x∈G rate(c K , x),
where "rate()" refers to the transitions in X .

The last picture can be simplified as follows:

c K c K +1 • • • c L • • • λ K µ K +1 λ K +1 µ K +2 λ L-1 µ L+1 λ L µ L+2 j µ (j) K G X (j) ≡ X (j)
We have µ

(j) K = x∈G rate(c K , x),
where "rate()" refers to the transitions in X .

Observe that the rates λ K , λ K +1 , . . . , µ K +1 , . . . don't change if j ∈ G changes.

Second main idea

• Assume first that two reals ρ 1 and ρ 2 are available, such that for all state x we have 0 ≤ ρ 1 ≤ r x ≤ ρ 2 < ∞.

• Assume also that we can build upper and lower bounds of the exact (and unknown) rates λ L and µ L , L ≥ K .

First case

First case: finite models, or infinite models with bounded rewards.

• Using previous results and some algebra, we obtain

ρ 1 + min j∈G x∈G (r x -ρ 1 )y (j) x ≤ R ≤ ρ 2 -max j∈G x∈G (ρ 2 -r x )y (j)
x .

Second case

Second case: infinite models with unbounded rewards (from Mahévas and Rubino, Bound computation of dependability and performability measures, IEEE Trans. Comp. 50 (5), 2001).

• [R] lb : basically as before

• for [R] ub , let X (j) denote the pseudo-aggregation of X (j) when G c is entirely collapsed into a single state c. • Let Z (j) be the pseudo-aggregation of Y (j) when the set of states {c K , c K +1 , . . .} is collapsed into a single state c, with stationary distribution z (j) . • Let Θ K = 1 and for I > K ,

Θ I = I L=K +1 [λ L-1 ] ub [µ L ] lb .
• The only parameter of Z (j) that must be computed is ν j = rate(c, j); it is given by

ν j = [µ K ] lb I ≥K Θ I .
• We need to use some r L ≥ r i , for all i ∈ C L .

• Define

r c = max max i∈G r i , L≥K Θ L r L L≥K Θ L • Then, we have R ≤ max j∈G x∈G r x z (j) x + r c z (j) c
.

Introduction Initial technique

Improvements

Basically only one linear system

• The following result then holds:

y (j) = 1 s + t j 1 j M, s, s Θ K +1 D , s Θ K +2 D , • • • where D = I ≥K Θ I . • In the same way, π (j) = 1 s + t j
(1 j M, s) .

(cont.)

To see how to apply this, consider, for instance, the bounds in the first case.

•

i .

• This basically reduces to compute 1 j Mγ T and 1 j M1 T . This means a fixed number of linear systems to solve, all involving the same matrix A G . The exact scheme depends on the solving technique we use.

; new approach

• The starting point was min j∈G R (j) ≤ R ≤ max j∈G R (j)

• and then, to look for some min j∈G R (j) lb and max j∈G R (j) ub .

• Now, we can use the obtained explicit expressions to be more precise.

• Let us consider, for instance, the case of [R] ub when ρ 2 < ∞.

• Using an upper bound ρ of the rewards on the set G c and working on the state space G + c, R (j) ≤ 1 j Mr T G + sρ s + t j .

where r G is the (row) vector of rewards inside G (cont.)

• ; R ≤ j∈G α j (1 j Mr T G ) s + t + s s + t ρ.

• Looking at the sign of the derivatives of this upper bound w.r.t. the different parameters, we obtain that replacing the exact and unknown rates by upper of lower bounds, we obtain a new and computable bound. • For instance, ∂ ∂s s s + t = t (s + t) 2 > 0, so, using the previous auxiliary chains that "push the mass to the right" we obtain s * ≥ s and this implies s s + t ≤ s * s * + t .

(cont.)

• We also can write s * s * + t ≤ s * s * + min j∈G t j

• A more complex expression can be derived in the same way for the second term of the bound.

  To obtain [R] lb and [R] ub , we must compute something of the form min

•

  Consider first the E 2 /M/1/H queue, with Erlang-2 inter-arrival distribution with parameter η and service rate µ. • This is easy to solve numerically, of course. The phased representation of this model is a Markov chain with 2(H + 1) states,

	Example 1 Example 2
	type 1
	type 1 • Consider first the E 2 /M/1/H queue, with Erlang-2 inter-arrival distribution with parameter η and service rate µ. l1
	• This is easy to solve numerically, of course. The phased delay
	representation of this model is a Markov chain with 2(H + 1) states, repair facility mu
	• Just for checking purposes, if I take a light traffic example using l1
	η = 9.0, µ = 8.0 and H = 100, and if the target is M = mean
	l2 number of customers, in equilibrium, we obtain with our method, for instance, [M] lb = 1.0271 and [M] ub = 1.3253 solving models having mu
	approximately 25% of states than X (exact value: M ≈ 1.0272).
	• With models having around 1/3 of X 's states, we get [M] lb = [M] ub , l2
	that is, = 1.0272. type 2
	type 2

•

  If the target is the asymptotic availability, look at the following results:

					Example 3
	lambda	nu	nu		nu	nu
		# of aux. states	lower bound	upper bound
		226		0.9997597121 0.9997597466
		1826		0.9997597349 0.9997597349

•

  Muntz, De Souza e Silva and Goyal, Bounding Availability of Repairable Computer Systems, IEEE Trans. Comp. 38 (12), 1989

Jan. 2020 (Denver, JMM'20)Bounds -Rubino

Context

• performance (or dependability, or performability) analysis

• systems in equilibrium

Context

• performance (or dependability, or performability) analysis

• systems in equilibrium

• continuous time Markov rewards models

• the underlying Markov chain is homogeneous and irreducible

• the state space is very large, possibly infinite

Context

• performance (or dependability, or performability) analysis

• systems in equilibrium

• continuous time Markov rewards models

• the underlying Markov chain is homogeneous and irreducible

• the state space is very large, possibly infinite

• there is no closed-form expression of π • Goal: accurate numerical analysis in spite of previous points

Key result

• That is, the state space of X is partitioned into (G , G c ).

• In X (j) we force all transitions from G c to G to enter G by the same state j. The stationary distribution of X (j) ix π (j) . • G , G c , j ∈ G are arbitrary.

Jan. 2020 (Denver, JMM'20)

Bounds -Rubino

Who is G ?

• Consider, for instance, that X models a queueing network.

• Let ν(x) = # of customers in some subnetwork of the model when the state, in equilibrium, is x. We want to know, for instance, the mean number of customers in that subnetwork, in equilibrium, that is, E(ν(X ∞ )).

Jan. 2020 (Denver, JMM'20) Bounds -Rubino 20 / 38

Key results

• For each j ∈ G define the Markov chain Y (j) by

G .

• Then, we have the two key following results:

New results

• A critical performance issue of this approach is the number of Y (j) (or Z (j) ) chains to be solved.

G where A G is the restriction of the infinitesimal generator of any of the considered chains to the states in G .

• Let s denote the mean sojourn time of X in G c .

• Denote by t j = E j (sojourn time of X in G ).

It is computable: t j = 1 j M1 T , where 1 j is the jth vector of the canonical base (that is, 1 j M is the jth row of M).

Second improvement

We can go a step further and prove that

where:

Conclusions

• This method improves the efficiency (precision×cost) of the previously published techniques.

• The key result is to make explicit some key quantities in the analysis, leading to a more precise bounding technique. • Weakest point: the same as in our previous work, the computation of lower bounds of transition rates between lumped states (in a pseudo-aggregation). • Future work: explore models where the mass is not necessarily "in the left of the space".