Interference cognizant network scheduling

Patent metadata

Field	Value
Publication number	US-9769075-B2
Application number	US-201514676464-A
Country	US
Kind code	B2
Filing date	Apr 1, 2015
Priority date	Apr 1, 2015
Publication date	Sep 19, 2017
Grant date	Sep 19, 2017

Abstract

Systems and methods for interference cognizant network scheduling are provided. In certain embodiments, a method of scheduling communications in a network comprises identifying a bin of a global timeline for scheduling an unscheduled virtual link, wherein a bin is a segment of the timeline; identifying a pre-scheduled virtual link in the bin; and determining if the pre-scheduled and unscheduled virtual links share a port. In certain embodiments, if the unscheduled and pre-scheduled virtual links don't share a port, scheduling transmission of the unscheduled virtual link to overlap with the scheduled transmission of the pre-scheduled virtual link; and if the unscheduled and pre-scheduled virtual links share a port: determining a start time delay for the unscheduled virtual link based on the port; and scheduling transmission of the unscheduled virtual link in the bin based on the start time delay to overlap part of the scheduled transmission of the pre-scheduled virtual link.

First claim

What is claimed is:

1. A method of scheduling communications in a network, the method comprising:
identifying a bin of a global timeline in which to schedule an unscheduled virtual link, wherein in a bin is a segment of the global timeline;
identifying a pre-scheduled virtual link in the bin;
determining if the pre-scheduled virtual link and the unscheduled virtual link share a common dispatch port at one or more nodes in the network;
if the unscheduled virtual link and the pre-scheduled virtual link do not share a common dispatch port, scheduling transmission of the unscheduled virtual link in the bin to overlap with the scheduled transmission of the pre-scheduled virtual link; and
if the unscheduled virtual link and the pre-scheduled virtual link share a common dispatch port:
determining a start time delay for the unscheduled virtual link based on the common dispatch port; and
scheduling transmission of the unscheduled virtual link in the bin based on the start time delay to overlap at least a portion of the scheduled transmission of the pre-scheduled virtual link.

2. The method of claim 1 , further comprising calculating a respective variable slot time duration for each of a plurality of virtual links for synchronization traffic and time triggered traffic.

3. The method of claim 1 , further comprising scheduling at least one scheduled rate constrained (SCHRC) virtual link on a respective local timeline of a transmitting end station from which the at least one SCHRC virtual link is transmitted, wherein the local timeline is not tied to the global timeline.

4. The method of claim 1 , wherein scheduling transmission of the unscheduled virtual link further comprises scheduling transmission of the unscheduled virtual link based on a maximum interference parameter, wherein the maximum interference parameter indicates the total number of occurrences of interference between the unscheduled virtual link and another scheduled virtual link which are permitted along the routing path for the unscheduled virtual link, the maximum interference parameter being an integer greater than or equal to zero.

5. The method of claim 1 , wherein identifying the bin comprises identifying a lowest utilized bin of a plurality of bins, wherein the lowest utilized bin has fewer scheduled virtual links than the other bins of the plurality of bins.

6. The method of claim 1 , wherein for left-justification configuration, when two bins of a plurality of bins have the same or similar utilization, selecting the bin of the two bins which appears earlier on the global timeline; and
for right-justification configuration, when two bins of the plurality of bins have the same or similar utilization, selecting the bin of the two bins which appears later on the global timeline.

7. The method of claim 1 , further comprising:
generating a respective configuration table for each of a plurality of switches to enable a respective test port in each of the plurality of switches; and
excluding the respective test port in each switch from the determination of whether the pre-scheduled virtual link and the unscheduled virtual link share a common dispatch port.

8. The method of claim 1 , further comprising:
splitting a payload of a message corresponding to a given virtual link into a plurality of fragments, each fragment being smaller than a maximum frame size; and
sending each of the plurality of fragments in a respective period of the given virtual link.

9. The method of claim 1 , wherein the pre-scheduled virtual link corresponds to a first protocol and the unscheduled virtual link corresponds to a second protocol different from the first protocol.

10. The method of claim 9 , wherein the first protocol is an Avionics Full-Duplex Switched (AFDX) Ethernet protocol and the second protocol is a Time-Triggered Ethernet protocol.

11. The method of claim 1 , further comprising assigning each of a plurality of virtual links a local priority at each node along the respective routing path of each virtual link.

12. A method of scheduling communications in a network, the method comprising:
identifying a bin of a global timeline in which to schedule a two or more virtual links, wherein in a bin is a segment of the global timeline;
determining if the two or more virtual links share a common port at one or more nodes in the network;
if the two or more virtual links do not share a common port, scheduling transmission of the two or more virtual links in the bin to overlap with each other; and
if the two or more virtual links share a common port:
determining a respective start time delay for each of the two or more virtual links based on the common port; and
scheduling a respective slot time for transmission of the two or more virtual links in the bin based on the respective start time delay for each of the two or more virtual links such that at least a portion of the respective slot times of the two or more virtual links overlap.

13. The method of claim 12 , further comprising calculating a respective variable slot time duration for the respective slot time of each of the two or more virtual links.

14. The method of claim 12 , wherein identifying the bin comprises identifying a lowest utilized bin of a plurality of bins, wherein the lowest utilized bin has fewer scheduled virtual links than the other bins of the plurality of bins.

15. The method of claim 12 , wherein scheduling the respective slot time for transmission of the two or more virtual links further comprises scheduling the respective slot time for transmission of the two or more virtual links based on a maximum interference parameter, wherein the maximum interference parameter indicates the total number of occurrences of interference between the two or more virtual links which are permitted along the respective routing path for each of the two or more virtual links, the maximum interference parameter being an integer greater than or equal to zero.

16. A program product comprising a non-transitory processor-readable medium on which program instructions are embodied, wherein the program instructions are configured, when executed by at least one programmable processor, to cause the at least one programmable processor to:
identify a bin of a global timeline in which to schedule an unscheduled virtual link, wherein in a bin is a segment of the global timeline;
identify a pre-scheduled virtual link in the bin;
determine if the pre-scheduled virtual link and the unscheduled virtual link share one or more common dispatch ports at one or more nodes in the network;
if the unscheduled virtual link and the pre-scheduled virtual link do not share the one or more common dispatch ports, schedule transmission of the unscheduled virtual link in the bin to overlap with the scheduled transmission of the pre-scheduled virtual link; and
if the unscheduled virtual link and the pre-scheduled virtual link share the one or more common dispatch ports:
determine a start time delay for the unscheduled virtual link based on an earliest common dispatch port among the one or more common dispatch ports; and
schedule transmission of the unscheduled virtual link in the bin based on the start time delay to overlap at least a portion of the scheduled transmission of the pre-scheduled virtual link.

17. The program product of claim 16 , wherein the program instructions are further configured to cause the at least one programmable processor to calculate a respective variable slot time duration for each of a plurality of virtual links.

18. The program product of claim 16 , wh

Assignees

• Honeywell Int Inc

Inventors

• Varadarajan Srivatsan
• Hall Brendan
• Smithgall William Todd
• Bonk Ted
• Delay Benjamin F

Classifications

• H04L47/28

  in relation to timing considerations · CPC title

• H04L12/6418

  Hybrid transport · CPC title

• H04L2012/6451

  Deterministic, e.g. Token, DQDB · CPC title

• H04L12/4015 Primary

  by scheduling the transmission of messages at the communication node · CPC title

• H04L47/12 Primary

  Avoiding congestion; Recovering from congestion · CPC title