System and method for identifying performance characteristics in asynchronous networks

Patent metadata

Field	Value
Publication number	US-9887928-B2
Application number	US-201514743471-A
Country	US
Kind code	B2
Filing date	Jun 18, 2015
Priority date	Jun 18, 2015
Publication date	Feb 6, 2018
Grant date	Feb 6, 2018

Abstract

A system for determining a worst case latency for a specific information flow that is part of a plurality of information flows and a worst case backlog for a specific queue that is part of a plurality of queues is disclosed. The plurality of information flows and plurality of queues are part of a configuration. The system performs operations including determining a maximum busy period length for the configuration. The operations include determining a set of candidate starting times for the configuration based on the maximum busy period length. The operations further include determining a maximum layout for a plurality of information flows within the configuration. The operations include updating the worst case latency and the worst case backlog based on the maximum layout. Finally, the operations include determining the worst case latency for the specific information flow and the worst case backlog for a specific queue.

First claim

What is claimed is:

1. A system for determining a worst case latency for a specific information flow of a plurality of information flows, wherein the plurality of information flows are part of a configuration for an asynchronous deterministic network, the system comprising:
a processor in communication with a display; and
a memory storing a scheduler and instructions executable by the processor to perform operations comprising:
determining a spare servicing capacity of the configuration by subtracting a maximum servicing capacity of the system by a sum of processing demands for all the plurality of information flows;
in response to determining no spare servicing capacity is available, setting an initial maximum busy period length as a maximum busy period length, wherein a busy period represents a time span during which the asynchronous deterministic network is busy processing incoming fragments without idling and the maximum busy period length represents a maximum length of all possible busy periods within a given period of time of the configuration;
in response to determining available spare servicing capacity, determining the maximum busy period length for the configuration by selecting one of the initial maximum busy period length and an alternate busy period, wherein the alternate busy period is determined based on the sum of the processing demands for all the plurality of information flows;
determining a set of candidate starting times for the configuration based on the maximum busy period length;
determining, based on the set of candidate starting times, a maximum layout for the plurality of information flows within the configuration except for the specific information flow;
updating the worst case latency based on the maximum layout;
determining the worst case latency for the specific information flow based on the updated worst case latency; and
generating a graphic representing the worst case latency upon the display, wherein the worst case latency is used by a verification process of performance characteristics of the system.

2. The system of claim 1 , wherein the set of candidate starting times begins at a start of a given period and includes a length equal to the maximum busy period length.

3. The system of claim 1 , wherein each candidate starting time in the set of candidate starting times is located within a given period starting at a time of zero, and includes a length equal to the maximum busy period length.

4. The system of claim 3 , wherein a minimum offset of the specific information flow is located no earlier than a beginning time of a single arrival window of the configuration, and wherein at most a single batch of fragments arrive within the single arrival window for the specific information flow.

5. The system of claim 1 , wherein updating the worst case latency includes making a copy of a layout of the configuration, and wherein the copy of the layout is a working layout.

6. The system of claim 5 , wherein updating the worst case latency includes adding a number of batches to the working layout, and wherein the number of batches is a total number of batches within the specific information flow.

7. The system of claim 6 , wherein updating the worst case latency includes determining a second worst case latency, and wherein the worst case latency is based on a set of schedules generated by the scheduler.

8. The system of claim 1 , wherein the specific information flow includes at least one message, and the at least one message includes at least one fragment, and wherein the at least one message is added to the configuration as a batch of fragments.

9. A system for determining a worst case backlog of a queue in a configuration for an asynchronous deterministic network, wherein the configuration includes a plurality of queues, the system comprising:
a processor in communication with a display; and a memory storing a scheduler and instructions executable by the processor to perform operations comprising: determining a spare servicing capacity of the configuration by subtracting a maximum servicing capacity of the system by a sum of processing demands for all the plurality of information flows;
in response to determining no spare servicing capacity is available, setting an initial maximum busy period length as a maximum busy period length, wherein a busy period represents a time span during which the asynchronous deterministic network is busy processing incoming fragments without idling and the maximum busy period length represents a maximum length of all possible busy periods within a given period of time of the configuration;
in response to determining available spare servicing capacity, determining the maximum busy period length for the configuration by selecting one of the initial maximum busy period length and an alternate busy period, wherein the alternate busy period is determined based on the sum of processing demands for all the plurality of information flows;
determining a set of candidate starting times for the configuration based on the maximum busy period length;
determining, based on the set of candidate starting times, a maximum layout for a plurality of information flows within the configuration;
updating the worst case backlog with the maximum layout;
determining the worst case backlog based on the updated worst case backlog; and
generating a graphic representing the worst case backlog upon the display, wherein the worst case backlog is used by a verification process of performance characteristics of the system.

10. The system of claim 9 , wherein the set of candidate starting times begins at a start of a given period and includes a length equal to the maximum busy period length.

11. The system of claim 9 , wherein each candidate starting time in the set of candidate starting times is located within a given period starting at a time of zero, and includes a length equal to the maximum busy period length.

12. The system of claim 11 , wherein a minimum offset of a specific information flow is located no earlier than a beginning of a single arrival window of the configuration, and wherein at most a single batch of fragments arrive within the single arrival window for the specific information flow.

13. The system of claim 9 , wherein updating the worst case backlog with the maximum layout includes determining an accumulated arrival volume and an accumulated departure volume for each queue in the configuration.

14. The system of claim 13 , wherein the accumulated arrival volume is determined for each queue in the configuration at distinct arrival times in a specific schedule, and wherein the specific schedule is part of a set of schedules.

15. The system of claim 13 , wherein the accumulated departure volume is determined for each queue in the configuration at distinct departure times in a specific schedule, and wherein the specific schedule is part of a set of schedules.

16. The system of claim 9 , wherein the queues each include at least one information flow, and wherein each information flow is assigned to a single queue and includes a sequence of at least one message generated from a single source at a given rate.

17. A non-transitory computer readable medium for determining a worst case latency for a specific information flow that is part of a plurality of information flows of a configuration, the computer readable medium comprising a computer program that when executed by a computer, causes the computer to:
determine a spare servicing capacity of the configuration by subtracting a maximum servicing capacity of the system by a sum of p

Assignees

• Boeing Co

Inventors

• Wang Changzhou
• Wang Guijun
• Nordsieck Arnold W
• Ling Yong Long Calvin

Classifications

• H04L47/00

  Traffic control in data switching networks (arrangements for detecting or preventing errors in the information received H04L1/00) · CPC title

• H04L43/0852

  Delays · CPC title

• H04L47/56 Primary

  implementing delay-aware scheduling · CPC title

• H04L47/621

  Individual queue per connection or flow, e.g. per VC · CPC title