Method for dynamic resource scheduling of programmable dataplanes for network telemetry

Patent metadata

Field	Value
Publication number	US-12248477-B2
Application number	US-202318097147-A
Country	US
Kind code	B2
Filing date	Jan 13, 2023
Priority date	Sep 29, 2021
Publication date	Mar 11, 2025
Grant date	Mar 11, 2025

Abstract

A method for network dataplane telemetry includes: a) receiving telemetry queries, where each query includes a requested network telemetry task, and associated query result accuracy and query result latency weights; b) every epoch, scheduling the telemetry queries to produce a schedule associating to each sub-epoch of an epoch for a subset of the telemetry queries; c) every sub-epoch, reprogramming a programmable dataplane device to execute scheduled telemetry queries associated the sub-epoch; d) every sub-epoch, collecting and aggregating intermediate query results from the programmable dataplane device; e) every epoch, returning aggregated results of completed queries; wherein scheduling the telemetry queries uses a multi-objective optimization that uses multiple objective functions weighted by the query result accuracy and query result latency weights to balance resource requirements of the runtime programmable network switch, query result accuracy, and query result latency.

First claim

The invention claimed is:

1. A computer-implemented method for network dataplane telemetry performed by a scheduler and a runtime component connected to a programmable dataplane device that generates aggregate traffic features from raw network packets in a data network;
the method comprising:
(a) receiving by the scheduler telemetry queries, where each query of the telemetry queries includes
i) a requested network telemetry task expressed as a sequence of filter and reduce operators, and
ii) associated query result accuracy and query result latency weights;

(b) scheduling by the scheduler the telemetry queries to produce a schedule,
wherein the scheduling is performed at a start of each processing time window (called an epoch) of a sequence of schedule processing time windows,
wherein the epoch is temporally divided into a sequence of equal duration sub-epochs,
wherein the schedule assigns a subset of the telemetry queries to each sub-epoch of the sequence of equal duration sub-epochs;

(c) reprogramming by the runtime component the programmable dataplane device to execute scheduled telemetry queries assigned to each sub-epoch of the sequence of equal duration sub-epochs in accordance with the schedule,
wherein the reprogramming is performed for each sub-epoch of the sequence of equal duration sub-epochs;

(d) collecting and aggregating by the runtime component intermediate query results from the programmable dataplane device,
wherein the collecting and aggregating is performed for each sub-epoch of the sequence of equal duration sub-epochs,
wherein the intermediate query results comprise aggregate traffic features generated from raw network packets by the programmable dataplane device in response to the scheduled telemetry queries;

(e) returning by the runtime component aggregated results of completed queries,
wherein the returning is performed for each epoch of the sequence of schedule processing time windows;
wherein scheduling the telemetry queries comprises solving a multi-objective optimization problem that uses multiple objective functions weighted by the query result accuracy and query result latency weights associated with the telemetry queries.

2. The method of claim 1 wherein solving the multi-objective optimization problem trades off query result accuracy for reduced resource requirements of the runtime programmable network switch by sampling a subset of the sequence of equal duration sub-epochs in which to execute a particular query, and trades off query result latency for reduced resource requirements of the runtime programmable network switch by executing operations of the particular query across several epochs.

3. The method of claim 1 wherein the programmable dataplane device is a network probe device adapted to generate aggregate traffic features from raw network packets.

4. The method of claim 1 wherein the programmable dataplane device is a semi-programmable hardware switching ASIC, fully-programmable hardware switching ASIC, a FPGA programmed to implement a dataplane probe interface, a programmable NIC, a software network switch, or a network device implementing software packet capture.

Assignees

• Univ Oregon
• Niksun Inc

Inventors

• Rejaie Reza
• Durairajan Ramakrishnan
• Misa Christopher H
• Willinger Walter

Classifications

• G06F16/2462

  Approximate or statistical queries · CPC title

• G06F16/24578

  using ranking · CPC title

• H04L43/08

  Monitoring or testing based on specific metrics, e.g. QoS, energy consumption or environmental parameters · CPC title

• G06F9/4881

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · CPC title

• G06F9/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) · CPC title