# US 11,451,492 B2 · Methods, systems, and apparatuses for enhanced parallelism of time-triggered ethernet traffic using interference-cognizant network scheduling > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,451,492 B2 - Document ID: US11451492B2 - Status: Granted - Kind: B2 - Application number: 17/130,624 - Filed: 2020-12-22 - Published: 2022-06-23 - Granted: 2022-09-20 - Earliest claimed: 2020-12-22 - Assignees: Honeywell International Inc. - Applicants: Honeywell International Inc. - Inventors: Benjamin F. DeLay; William T. Smithgall - Web page: https://patentgrep.com/patent/US11451492B2 ## CPC - H04L 12/4015: {by scheduling the transmission of messages at the communication node} - H04L 49/70: {Virtual switches} - H04L 47/20: Traffic policing - H04L 47/22: Traffic shaping - H04L 47/24: Traffic characterised by specific attributes, e.g. priority or QoS - H04L 47/2416: Real-time traffic - H04L 47/2425: for supporting services specification, e.g. SLA - H04L 47/28: in relation to timing considerations - H04L 47/50: Queue scheduling - H04L 49/254: {Centralised controller, i.e. arbitration or scheduling} - H04L 49/354: for supporting virtual local area networks [VLAN] - 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 pre-processing, by a scheduling algorithm implemented by a Network Scheduling Tool (NST), VL information prior to initiating a scheduling procedure by, detecting VL information associated with VLs that having common physical resources that include a common direction of a switching port or an egress end system port; and storing the VL information associated with the set of VLs for retrieval by the NST to parse a VL list for scheduling to determine one or more conflicting VLs in functionalities with a VL that is to be scheduled by a first pass that attempts favoring scheduling a VL into a bin when previously scheduled VLs fail to exhibit conflicts; and a second pass that attempts to resolve at least one conflict exhibited in the scheduling procedure by offsetting a transmit time. ## Claims ### Claim 1 A method for pre-processing scheduling of Virtual Links (VLs) contained in a Time-Triggered Ethernet (TTE) network in predefined priority order for use by a Network Scheduling Tool (NST), the method comprising: pre-processing, by a scheduling algorithm implemented by the NST, VL information prior to initiating a scheduling procedure of a set of VLs, the pre-processing by the scheduling algorithm by the NST comprising the steps of: detecting VL information associated with the set of VLs that utilize one or more common physical resources of the TTE network wherein the one or more common physical resources at least comprise a common direction of a switching port or an egress end system port; storing the VL information associated with the set of VLs in a memory for retrieval by the NST to parse a VL list for scheduling by the scheduling algorithm to determine one or more conflicting VLs in functionalities during the scheduling procedure; scheduling a first pass of a two-pass procedure of the set of VLs that attempts to favor scheduling a VL into a bin when a previously scheduled VL fails to exhibit conflicts with the VL that is scheduled; and scheduling a second pass of the two-pass procedure of the set of VLs that attempts to resolve at least one conflict exhibited in the scheduling procedure by offsetting a transmit time of the VL that is scheduled. ### Claim 2 (depends on 1) The method of claim 1, further comprising: performing the two-pass procedure of the set of VLs by the scheduling algorithm for identifying and prioritizing a physical resource contention between the set of VLs. ### Claim 3 (depends on 2) The method of claim 2, further comprising: configuring the NST with conflict detection logic comprising a double-sided timing window for resolving a physical resource conflict between the VL that is to be scheduled and each VL already scheduled in the bin. ### Claim 4 (depends on 3) The method of claim 3, wherein the double-sided timing window comprises a transmit range defined by a transmit-no-later-than time and a transmit-no-earlier-than time. ### Claim 5 (depends on 4) The method of claim 4, further comprising: aggregating a plurality of summing ranges wherein each summing range is defined by a set of aggregated non-conflicting timing windows between a VL that is to be scheduled, and a set comprising previously scheduled conflicting VLs within the bin. ### Claim 6 (depends on 5) The method of claim 5, further comprising: determining in each summing range, a location for placement of the VL that is to be scheduled within the bin. ### Claim 7 (depends on 6) The method of claim 6, further comprising: excluding one or more destination ports with conflicts determined by the conflict detection logic. ### Claim 8 (depends on 7) The method of claim 7, further comprising: in response to excluding conflicted destination ports, queuing a set of egress VLs at switch interlink ports for servicing a destination end system while preserving a high-fidelity conflict detection and resolution pertaining to each set of switch interlink ports. ### Claim 9 (depends on 8) The method of claim 8, further comprising: determining a worst-case serialization delay based on a link rate at an excluded conflicted destination port, of approximately all existing scheduled traffic at a specific port in the bin which is at proximity to an end of the bin wherein if a scheduled VL causes a queuing delay extending beyond a bin boundary, then not proceeding to schedule the VL within the bin. ### Claim 10 (depends on 9) The method of claim 9, further comprising: allowing a tolerance of a larger queuing delay if the scheduling of a serialized transmission to a destination end system of a final VL that is scheduled at an end of the bin has already been initiated but has yet been completed. ### Claim 11 (depends on 10) The method of claim 10, further comprising: post-scheduling by parsing a priority-sorted list for discovering a VL of a set of VLs that do not conflict with a just scheduled VL or any previously scheduled VLs within the bin, wherein the scheduling algorithm places any non-conflicting VLs in a same bin as a just-scheduled VL if the bin represents a valid placement for the VL based on input system timing constraints. ### Claim 12 A system for pre-processing scheduling of Virtual Links (VLs) contained in a Time-Triggered Ethernet (TTE) network in predefined priority order for use by a Network Scheduling Tool (NST), wherein the NST comprises: one or more processors to pre-process VL information prior to initiation of a scheduling procedure of a set of VLs to: one or more processors to detect VL information associated with the set of VLs that utilize one or more common physical resources of the TTE network wherein the one or more common physical resources at least comprise a common direction of a switching port or an egress end system port; one or more processors to store the VL information associated with the set of VLs in a memory for retrieval by the NST to parse a VL list for scheduling by the scheduling algorithm to determine one or more conflicting VLs in functionalities during the scheduling procedure; and one or more processors to perform a two-pass procedure by the scheduling algorithm to identify and prioritize a physical resource contention between the set of VLs wherein a first pass of the two-pass procedure attempts to favor to schedule a VL into a bin when all previously scheduled VLs fail to exhibit a conflict with the VL that is to be scheduled wherein a second pass of the two-pass procedure for a set of VLs attempts to resolve any conflicts by an offset of a transmit time of the VL that is to be scheduled. ### Claim 13 (depends on 12) The system of claim 12, wherein the NST further comprises: one or more processors to implement conflict detection logic which comprises a double-sided timing window for resolving a physical resource conflict between the VL that is to be scheduled and each VL already scheduled in the bin wherein the double-sided timing window comprises a transmit range defined by a transmit-no-later-than time and a transmit-no-earlier-than time; and one or more processors to aggregate, by the scheduling algorithm, based on a sum of ranges defined by aggregated non-conflicting timing windows between a VL that is to be scheduled, and approximately all of the previously scheduled and conflicted VLs within the bin that determines a location for placement of the VL in the bin. ### Claim 14 (depends on 13) The system of claim 13, wherein the NST further comprises: one or more processors to exclude, by the scheduling algorithm, one or more destination ports with conflicts via the conflict detection logic; in response to excluding conflicted destination ports, one or more processors to queue by the scheduling algorithm of a set of egress VLs at switch interlink ports to service a destination end system and to preserve a high-fidelity conflict detection and a resolution which pertains to each set of switch interlink ports; one or more processors to determine, by the scheduling algorithm, a worst-case serialization delay based on a link rate at an excluded conflicted destination port, of approximately all existing scheduled traffic at that specific port in the bin which are in proximity to an end of the bin wherein if the to be scheduled VL causes a queuing delay which extends beyond a bin boundary, then not continuing to schedule the VL in the bin; and one or more processors to allow, by the scheduling algorithm, a tolerance of a larger queuing delay if a schedule of a serialized transmission to a destination end system of a final VL that is to be scheduled at an end of a bin has already been initiated but has not yet been completed. ### Claim 15 (depends on 14) The system of claim 14, wherein the NST further comprises: one or more processors to post-schedule, by the scheduling algorithm, to parse a priority-sorted list to determine a VL of a set of all VLs that are not conflicted with a just scheduled VL or any previously scheduled VLs in the bin, wherein the scheduling algorithm places any non-conflicting VLs in a same bin as a just-scheduled VL if the bin represents a valid placement for the VL based on input system timing constraints. ### Claim 16 An apparatus comprising a network scheduling tool (NST) for pre-processing scheduling of Virtual Links (VLs) contained in a Time-Triggered Ethernet (TTE) network in predefined priority order for use by a Network Scheduling Tool (NST), comprising: the NST is configured with a processor programmed by a set of instructions to schedule time-triggered traffic by: pre-processing, by a scheduling algorithm of the NST, VL information prior to initiating a scheduling procedure of a group of VLs; detecting VL information associated with the group of VLs that utilize one or more common physical resources of the TTE network wherein the one or more common physical resources at least comprise a common direction of a switching port or an egress end system port; storing the VL information associated with the group of VLs in a memory for retrieval by the NST to parse a VL list for scheduling by the scheduling algorithm to determine one or more conflicting VLs in functionalities during the scheduling procedure; and performing a two-pass procedure by the scheduling algorithm for identifying and prioritizing a physical resource contention between a set of VLs by scheduling a first pass of the two-pass procedure of the set of VLs that attempts favoring scheduling a VL into a bin when previously scheduled VLs fail to exhibit conflicts with the VL that is to be scheduled, and by scheduling a second pass of the two-pass procedure of the set of VLs that attempts to resolve at least one conflict exhibited in the scheduling procedure by offsetting a transmit time of the VL that is to be scheduled.