# US 2019/0171484 A1 · Method and device for scheduling of dataflow components > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2019/0171484 A1 - Document ID: US20190171484A1 - Status: Published application - Kind: A1 - Application number: 16/324,544 - Filed: 2017-08-07 - Published: 2019-06-06 - Earliest claimed: 2016-08-09 - Assignees: Alcatel Lucent - Applicants: Alcatel Lucent - Inventors: Philippe Dobbelaere - Web page: https://patentgrep.com/patent/US20190171484A1 ## CPC - G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues} - G06F 9/5011: {the resources being hardware resources other than CPUs, Servers and Terminals} - G06F 9/5038: {considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration (scheduling strategies G06F9/4881 and subgroups)} - G06F 9/5072: {Grid computing} - G06F 9/5083: {Techniques for rebalancing the load in a distributed system} - G06F 9/546: {Message passing systems or structures, e.g. queues} - G06F 11/3006: {where the computing system is distributed, e.g. networked systems, clusters, multiprocessor systems (multiprogramming arrangements G06F9/46; allocation of resources G06F9/50)} - G06F 11/3414: {Workload generation, e.g. scripts, playback} - G06F 11/3447: {Performance evaluation by modeling} - H04L 47/25: with rate being modified by the source upon detecting a change of network conditions - G06F 2201/805: Real-time - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract Method and device for scheduling of dataflow components Embodiments relate to a method for scheduling dataflow components (6), executed by a scheduling device (4), comprising repeating the following steps for successive increasing input message rates (1/β): —applying (S1) an ingress message flow (F1) at an ingress message rate (1/β) to a distributed dataflow comprising at least one dataflow component (6) executed by respective processing devices (5), —determining (S2) a total latency (Δt) of at least one of dataflow component (6), and —determining (S3) a serving rate (μ) associated with said ingress message rate (1/β) for said at least one dataflow component (6), in function of said ingress message rate (1/β) and said total latency (Δt), until the scheduling device (4) is unable to determine a serving rate (μ) associated with the ingress message rate (1/β), thereby determining a maximum serving rate for said at least one dataflow component (6). ## Claims ### Claim 1 Method for scheduling dataflow components (6) of a distributed dataflow, executed by a scheduling device (4), wherein scheduling a dataflow component (6) comprises assigning a processing device (5) out of a plurality of processing devices (5) to said dataflow component (6), the method comprising repeating the following steps for successive increasing input message rates (1/β): applying (S1) an ingress message flow (F1) at an ingress message rate (1/β) to a distributed dataflow comprising at least one dataflow component (6) executed by respective processing devices (5), determining (S2) a total latency (Δt) of at least one of dataflow component (6), and determining (S3) a serving rate (μ) associated with said ingress message rate (1/β) for said at least one dataflow component (6), in function of said ingress message rate (1/β) and said total latency (Δt), until the scheduling device (4) is unable to determine a serving rate (μ) associated with the ingress message rate (1/β), thereby determining a maximum serving rate for said at least one dataflow component (6). ### Claim 2 (depends on 1) Method according to claim 1, wherein said maximum serving rate is the last serving rate determined before the scheduling device (4) is unable to determine a serving rate (μ). ### Claim 3 (depends on 1) Method according to claim 1, wherein determining (S2) a total latency (Δt) comprises identifying an input message associated with an output message of said at least one dataflow component, and determining a time lapse between the input message and the output message. ### Claim 4 (depends on 1) Method according to claim 1, comprising selecting an ingress message rates (1/β) equals to the serving rate associated with the previous ingress message rates (1/β). ### Claim 5 (depends on 1) Method according to claim 1, wherein determining said serving rate (μ) comprises solving an equations system modeling the total latency as a sum of a queuing latency and a processing latency in a D/M/1 queuing system. ### Claim 6 (depends on 1) Method according to claim 1, comprising scheduling a dataflow component (6) in function of the determined maximum serving rate. ### Claim 7 (depends on 6) Method according to claim 6, wherein scheduling a dataflow component comprises: determining (T1) a processor utilization of the dataflow component (6) in function of the determined maximum serving rate, and selecting (T2) a processing device (5) such that a sum of the current processor utilization of the processing device (5) and the determined processor utilization of the dataflow component is below a predetermined threshold. ### Claim 8 (canceled) ### Claim 9 Scheduling device for scheduling dataflow components of a distributed dataflow, wherein scheduling a dataflow component (6) comprises assigning a processing device (5) out of a plurality of processing devices (5) to said dataflow component (6), the scheduling device comprising means (7, 8, P) configured for repeating the following steps for successive increasing input message rates (1/β): applying (S1) an ingress message flow (F1) at an ingress message rate (1/β) to a distributed dataflow comprising at least one dataflow component (6) executed by respective processing devices (5), determining (S2) a total latency (Δt) of at least one of dataflow component (6), and determining (S3) a serving rate (μ) associated with said ingress message rate (1/β) for said at least one dataflow component (6), in function of said ingress message rate (1/β) and said total latency (Δt), until the scheduling device (4) is unable to determine a serving rate (μ) associated with the ingress message rate (1/β), thereby determining a maximum serving rate for said at least one dataflow component (6).