# US 2021/0067459 A1 · Methods, systems and appratuses for optimizing time-triggered ethernet (tte) network scheduling by using a directional search for bin selection

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0067459 A1
- Document ID: US20210067459A1
- Status: Published application
- Kind: A1
- Application number: 16/554,210
- Filed: 2019-08-28
- Published: 2021-03-04
- Earliest claimed: 2019-08-28
- Assignees: Honeywell International Inc.
- Applicants: Honeywell International Inc.
- Inventors: Benjamin F. DeLay; Srivatsan Varadarajan; Theodore J. Bonk; William T. Smithgall; Brent A. Morin
- Web page: https://patentgrep.com/patent/US20210067459A1

## CPC

- H04L 47/58: {Changing or combining different scheduling modes, e.g. multimode scheduling}
- H04L 47/125: by balancing the load, e.g. traffic engineering
- H04L 47/28: in relation to timing considerations
- H04L 47/765: triggered by the end-points
- H04L 49/3045: {Virtual queuing}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Methods, systems and apparatuses for scheduling a plurality of Virtual Links (VLs) in a Time-Triggered Ethernet (TTE) network by a network scheduling and configuration tool (NST) by establishing a collection of bins that corresponds to the smallest harmonic period allowing full network traversal of a time-triggered traffic packet in the network for determining available bin sets for sending the VL data by the NST; processing by a scheduling algorithm the VLs to be sent in accordance with a strict order comprising scheduling all the highest rate VLs prior to scheduling lower rate VLs; and scheduling reservations for the VLs in bins by tracking the available time available in each bin and optionally spreading the VL data across available bin sets by sorting a list of available bins by ascending bin utilization and by specifying a left-to-right or right-to-left sort order when searching for available bins based on a position in the timeline between the transmitter and receiver end stations.

## Claims

### Claim 1

A method of scheduling messages by implementing a network scheduling and configuration tool (NST), the method comprising:
receiving virtual links (VLs), global system inputs and localhost inputs by the NST for calculating a schedule for sending VLs based on a timeline of dispatch times from a transmitter end station to an arrival window at a receiver end station wherein the schedule is based on message rates, and timing constraints of size allocations of nodes in a scheduled path wherein the nodes comprise end stations and switches wherein the localhost inputs specify a sort order for available bins used in sending VL data across the nodes;
receiving scheduling instructions by the NST for computing a configuration implemented for stacking VLs for transmitting on a path between nodes and for scheduling tables loaded by the nodes;
establishing a collection of bins that corresponds to the smallest harmonic period allowing full network traversal of a time-triggered traffic packet in the network for determining available bin sets for sending the VL data by the NST;
processing by a scheduling algorithm the VLs to be sent in accordance with a strict order comprising scheduling all highest rate VLs prior to sending lower rate VLs; and
scheduling reservations for the VLs in bins by tracking an available time in each bin and optionally spreading the VL data across available bin sets by sorting a list of available bins by ascending bin utilization and by specifying a left-to-right or right-to-left sort order when searching for available bins based on a position in the timeline between the transmitter and receiver end stations.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
sub-dividing the VLs per one or more common rate groups of the scheduled rates of the plurality of VLs and scheduling the VLs in sorted order per common rate group.

### Claim 3 (depends on 2)

The method of claim 2, further comprising:
sorting bins of each common rate group within a VL's green zone based on the scheduling algorithm of optionally spreading the VL data across the available bin set, optionally sorted ascending by the bin utilization of each bin in the available bin set wherein the VL's green zone is a time box within a VL's transmit period based on available latency-related constraints.

### Claim 4 (depends on 3)

The method of claim 3, further comprising:
performing the ascending or descending sorting of each bin based on the bin utilization and by a bin index or a time locality of each bin.

### Claim 5 (depends on 4)

The method of claim 4, further comprising:
searching available bin space in the available bin set by either the specified left-to-right or right-to-left sort order to identify a first available bin for placing the VL reservation.

### Claim 6 (depends on 5)

The method of claim 5, further comprising:
placing the VL into a first bin of the available bin set in which the VL fits in accordance with the available bin space.

### Claim 7 (depends on 6)

The method of claim 6, further comprising:
placing a subsequent VL in a serial manner into another bin in the available bin set if there is time in another bin to place the subsequent VL.

### Claim 8 (depends on 7)

The method of claim 7, further comprising:
placing the VL in a non-interfering path with all other VLs in the available bin set and updating the bin utilization in the available bin set.

### Claim 9

A system for directional scheduling a plurality of Virtual Links (VLs) in a Time-Triggered ethernet network using a network scheduling tool (NST), the system comprising:
the NST configured to:
receive virtual links (VLs), global system inputs and localhost inputs by the NST to calculate a schedule to send VLs based on a timeline of dispatch times from a transmitter end station to an arrival window at a receiver end station wherein the schedule is based on message rates, and timing constraints of size allocations of nodes in a scheduled path wherein the nodes comprise end stations and switches wherein the localhost inputs specify a sort order for available bins used in sending VL data across the nodes;
receive scheduling instructions by the NST for computing a configuration implemented for stacking VLs for transmitting on a path between nodes and for scheduling tables loaded by the nodes;
establish a collection of bins that corresponds to the smallest harmonic period allowing full network traversal of a time-triggered traffic packet in the network for determining available bin sets for sending the VL data by the NST;
process by a scheduling algorithm the VLs to be sent in accordance with a strict order which comprises a schedule of all the highest rate VLs prior to sending lower rate VLs; and
schedule reservations for the VLs in bins by tracking an available time in each bin and to optionally spread the VL data across available bin sets by a sort of a list of available bins by ascending bin utilization and by a specification of a left-to-right or right-to-left sort order when a search is performed for available bins based on a position in the timeline between the transmitter and receiver end stations.

### Claim 10 (depends on 9)

The system of claim 9, further comprising:
the NST configured to:
sub-divide the VLs per one or more common rate groups of the scheduled rates of the plurality of VLs and to schedule the VLs in sorted order per common rate group.

### Claim 11 (depends on 10)

The system of claim 10, further comprising:
the NST configured to:
sort bins of each common rate group within the VL's green zone based on the scheduling algorithm of optionally spreading the VL data across the available bin set, sorted ascending by the utilization of each bin in the available bin set wherein the VL's green zone is a time box within a VL's transmit period based on available latency-related constraints.

### Claim 12 (depends on 11)

The system of claim 11, further comprising:
the NST configured to:
perform the ascending sorting of the bin set based on the bin utilization by a bin index or a time locality of each bin.

### Claim 13 (depends on 12)

The system of claim 12, further comprising:
the NST configured to:
search available bin space in the available bin set by either the specified left-to-right or right-to-left sort order to identify the first available bin to place the VL reservation.

### Claim 14 (depends on 13)

The system of claim 13, further comprising:
the NST configured to:
place the VL into a first bin of the available bin set in which the VL fits in accordance with the available bin space.

### Claim 15 (depends on 14)

The system of claim 14, further comprising:
the NST configured to:
place a subsequent VL in a serial manner into another bin in the available bin set if there is time in another bin to place the subsequent VL.

### Claim 16 (depends on 15)

The system of claim 15, further comprising:
the NST configured to:
place the VL in a non-interfering path with all other VLs in the available bin set and update the bin utilization in the available bin set.

### Claim 17

A directional scheduling apparatus comprising a network scheduling tool (NST) to schedule a plurality of Virtual Links (VLs) in a Time-Triggered Ethernet (TTE) network, comprising:
the NST configured with a processor programmed by a set of instructions to schedule time-triggered traffic in a green zone based on timing data available for the VLs, wherein the green zone is a time box within the VL's transmit period based on available latency-related constraints, to:
receive virtual links (VLs), global system inputs and localhost inputs by the NST to calculate a schedule to send VLs based on a timeline of dispatch times from a transmitter end station to an arrival window at a receiver end station wherein the schedule is based on message rates, and timing constraints of size allocations of nodes in a scheduled path wherein the nodes comprise end stations and switches wherein the localhost inputs specify a sort order for available bins used in sending VL data across the nodes;
receive scheduling instructions by the NST for computing a configuration implemented for stacking VLs for transmitting on a path between nodes and for scheduling tables loaded by the nodes;
establish a collection of bins that corresponds to the smallest harmonic period allowing full network traversal of a time-triggered traffic packet in the network for determining available bin sets for sending the VL data by the NST;
process by a scheduling algorithm the VLs to be sent in accordance with a strict order which comprises a schedule of all the highest rate VLs prior to sending lower rate VLs; and
schedule reservations for the VLs in bins by tracking an available time in each bin and to optionally spread the VL data across available bin sets by a sort of a list of available bins by ascending bin utilization and by a specification of a left-to-right or right-to-left sort order when a search is performed for available bins based on a position in the timeline between the transmitter and receiver end stations.

### Claim 18 (depends on 17)

The directional scheduling apparatus of claim 17, further comprising:
the NST configured to:
search available bin space in the available bin sets by either the specified left-to-right or right-to-left sort order to identify a first available bin to place the VL reservation.

### Claim 19 (depends on 18)

The directional scheduling apparatus of claim 18, further comprising:
the NST configured to:
place the VL into a first bin of the available bin set in which the VL fits in accordance with the available bin space.

### Claim 20 (depends on 19)

The directional scheduling apparatus of claim 19, further comprising:
the NST configured to:
place a subsequent VL in a serial manner into another bin in the available bin set if there is time in the available bin space of another bin to place the subsequent VL.
