System and method for identifying performance characteristics in asynchronous networks

Patent metadata

Field	Value
Publication number	US-2016373367-A1
Application number	US-201514743471-A
Country	US
Kind code	A1
Filing date	Jun 18, 2015
Priority date	Jun 18, 2015
Publication date	Dec 22, 2016
Grant date	—

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; and a memory storing a scheduler and instructions executable by the processor to perform operations comprising:
determining a maximum busy period length for the configuration;
determining a set of candidate starting times for the configuration based on the maximum busy period length;
determining 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; and
determining the worst case latency for the specific information flow.

2 . The system of claim 1 , wherein determining the maximum busy period length is based on a spare servicing capacity, and wherein the spare servicing capacity is determined by subtracting a maximum servicing capacity of the asynchronous deterministic network by a sum of processing demands for all the plurality of information flows.

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

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

5 . The system of claim 4 , wherein a minimum offset of the specific information flow is located no earlier than a beginning time of a specific arrival window of the configuration.

6 . 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.

7 . The system of claim 6 , 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.

8 . The system of claim 7 , 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.

9 . 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.

10 . 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; and a memory storing a scheduler and instructions executable by the processor to perform operations comprising:
determining a maximum busy period length for the configuration;
determining a set of candidate starting times for the configuration based on the maximum busy period length;
determining a maximum layout for a plurality of information flows within the configuration;
updating the worst case backlog with the maximum layout; and
determining the worst case backlog.

11 . The system of claim 10 , wherein determining the maximum busy period length is based on a spare servicing capacity of the configuration, and wherein the spare servicing capacity is determined by subtracting a maximum servicing capacity of the asynchronous deterministic network by a sum of processing demands for all the plurality of information flows.

12 . The system of claim 10 , 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.

13 . The system of claim 10 , wherein each candidate starting time in the set of candidate starting times are located within a given period starting at a time of zero, and include a length equal to the maximum busy period length.

14 . The system of claim 13 , wherein a minimum offset of a specific information flow is located no earlier than a beginning of an arrival window of the configuration.

15 . The system of claim 10 , 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.

16 . The system of claim 15 , 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.

17 . The system of claim 15 , 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.

18 . The system of claim 10 , 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.

19 . 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 maximum busy period length for the configuration; determine a set of candidate starting times for the configuration based on the maximum busy period length; determine a maximum layout for a plurality of information flows within the configuration except for the specific information flow; update the worst case latency based on the maximum layout; and determine the worst case latency for the specific information flow.

20 . The computer readable medium of claim 19 , wherein the computer is further caused to determine a worst case backlog of a queue in the configuration, wherein the worst case backlog is determined based on the maximum busy period length for the configuration, the set of candidate starting times for the configuration.

Assignees

• Boeing Co

Inventors

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

Classifications

• H04L47/56 Primary

  implementing delay-aware scheduling · CPC title

• H04L43/0852

  Delays · CPC title

• H04L47/621

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

• H04L47/00

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