Add New Modeling Capabilities: Domain-specific Models as Extensions of the Server Graph

[sbondorf]

The current DiscoDNC network backend (as of version 2.4) does not fully implement the entire network modeling stack of network calculus, see [1]. It is limited to the specific network representation required for an analysis.

Details: Currently the network backend is limited by the Network.java class. It offers a generic implementation storing a directed graph whose vertices represent servers and edges represent links -- classes exist for both these parts of a network. The server requires a service curve to be instantiated and thus it is intended to store a server graph only. Additionally, while flows must be routed in the server graph, finding reasonable paths is not possible without information about the device graph. Note that a device like a router can add multiple servers to the server graph, e.g., one for each of its output queues. Without a mapping to from devices to servers, the source and destination server (in case of output queueing even a server of the devices before the destination device) are simply not known. Besides routing, this lack of information inhibits a proper integration of turn prohibition that relies on the mapping of devices to servers in order to feed-forwardize the server graph (again, see [1] and the references therein).

Currently, a network instance can be used out of its indented context and take the role of a device graph. Yet, the Network class should rather take a superordinate role, i.e., be extended to store multiple representations (device graph, server graph, feed-forwardized server graph) and provide turn prohibition as well as routing between devices in the feed-forwardized server graph.

[1] Iterative Design Space Exploration for Networks Requiring Performance Guarantees (Bruno Cattelan, Steffen Bondorf), In IEEE/AIAA 36th Digital Avionics Systems Conference (DASC 2017), 2017.

[matyesz]

An idea (please evaluate): we could use xsd to create the network model and generate java code with jaxb. Pros:

1. xsd has visual editors so you edit the network model as an uml, easy to change
2. xml support out of the box - network can be described both in java or via xml (users have their data in db so it is easier for them to have an xml extract than java code). What do you think?

[sbondorf]

This issue is indeed closely related with having a proper storage format for the network. As both issues can be addressed individually, I opened issue #9 for this.

[matyesz]

Shouldn't we include configuration elements for the calculator in the new representation? I mean we could include CurveBackend information in the representation so the calculation method will not be coming from the Java code. The other option is to have a CLI tool and add options for the file and CurveBackend.

[sbondorf]

I would like to keep the network instance as unaware of its environment as possible. If we couple it too tightly with DiscoDNC-specific concepts, we might jeopardize code sharing with the DiscoSNC and other projects sharing at least two of our three "layers" of an entire network (the third, feed-forwardized server graph, might not be necessary for other applications). Admittedly, there is already some significant coupling as the Network class requires service/arrival curve instances to create servers and flows. Some time ago, I had a brief brainstorming session with @scriptkitty about relaxing this by introducing a more generic Resource interface that might be any curve or distribution, holding this information itself. Existing ideas are thus rather pulling into the opposite direction.

On the other hand, I thought about having a calculator config instance (similar to analysis config) instead of the current singleton, too. I think this would be a worthwhile improvement for the reason mentioned above: we could adapt method signatures to require providing them with everything they need -- instances of the right backends are currently missing. No queries to the superordinate calculator config are needed in this scenario, it need not be a singleton anymore. I feel we can achieve this with further extensions to the superordinate calculator class in branch v2.5. Probably in a way that a network instance can only exist in the context of a calculator instance?

[matyesz]

Network (model) must be decoupled from business logic. For this in the past we had a model to steup the network (VLs, switches, paths...) and a special timing model for the calculations (paths, servers...) so we could have different timing model for DiscoSNC and DiscoDNC while the model descriptor towards the users is exactly the same (they know BAG, max frame size but do not havean idea about service and arrival curves). With this we could have a new project called user_model that is the input of both DiscoDNC and DiscoSNC (a separatae maven dependency) and can decide on internal timing models later on. We can also decide to have thesame user and timing model but that is very hard as for calculations you need additional data as for just describing a network with VLs and paths and switches. We can go in a way that Calculator holds together a full calculation for a network (thus holding network, calculation config and all other things).

[sbondorf]

Clearly separating the network from the resource descriptions of DNC or SNC is definitely the solution to strive for. It also makes storing a network (#9) easier. As explicitly mentioned there, we then need 1+n files, one for the network and n for the n different resource descriptions. I expect that this shifts the complications to mapping the resources to the network components (e.g., service curve --> server, arrival curve --> flow). Dealing with this challenge, we can also start using an existing and maintained graph library again*, e.g., JGraphT or Guava. Maybe we can then leverage some storage functionality as well. Regarding the mapping, I am currently experiencing a similar problem on a smaller scale. When separating the results from the test classes for issue #15, there it is the mapping {delay bound, backlog bound} --> flow, yet, in order to get this right, we first need to get the flow instances from the network. A central entity holding all information and mapping accordingly is also needed there. I think having Calculator take that role for a new network backend is not only reasonable but actually required. I hope to push a first solution soon so we can use this code as a first investigation (spoiler: I have a working solution but it is ugly).

The network model consisting of switches is an abstraction above the server graph we use for analysis. That is, the device graph we derive a feed-forwardized server graph from. Adding modeling features that are known from standards, e.g., VLs, is a good idea. I am also frequently asked about just putting in the scheduler instead of a service curves -- another potential abstraction to put over our code in order to help users not into DNC details.

*Some history: The dnclib-1.x used the already end-of-life graph library JUNG 1.7.6 that was incompatible with JUNG 2.0 that, in turn, also seemed unmaintained for quite some years. Needing to rebuild the network backend anyway, I decided to couple it tightly to the DNC concepts in order to make progress fast. I am not opposing to revert this decision now the DiscoDNC is working quite well.

[sbondorf]

I pushed a branch to my sbondorf/DiscoDNC fork called test_results_separation where I work towards the "separation of config and logic" goal. Issues sbondorf/DiscoDNC#1 and sbondorf/DiscoDNC#2 detail my thoughts from above.

[matyesz]

My first proposal is the following:

I have introduced devices (switch, end-system ...) that have ports (mostly tx andrx ports, where txPort is the server with a given service curve. Each link is a physical connection between two ports. A flow contains several paths (like a VL is multicast) and a path is a combination of links after each other. With this approach it is easy to find circular paths in the flow Please review!

BTW: Should not we move the model to a separate module? As far as I understand it will used by other projects too.

[sbondorf]

Here are my thought. I'd be happy to hear from everyone possessing knowledge in, e.g., SNC (@scriptkitty @paulnikolaus @mbeck85) or systems (@fabgeyer) or ...

Network Entities

• You prefixed the ports according to their role with respect to the link connecting them, right? From my experience with the literature, I think they are better named according to their role within the device they belong to. I.e., I suggest renaming srcPort -> outPort and dstPort -> inPort to match output/input queueing assumptions.
  • Do we want a model with bidirectional links?
• Path being able to store multicast is definitely a welcome addition. Here, theory is ahead of tool support. If I remember correctly, this 1:n-solution matches the idea of Bruno Cattelan. Let me try to get him involved.
• Whereas links connect ports between devices, turns (e.g., over the switching fabric) connect ports within a single device.

Overall Design (I.e., how do we extend/integrate with the current code) I am also in favor of designing this model as a most generic module that resides in a separate project and can be reused by, for instance, the DiscoSNC. In order to do so, I think we should be more comprehensive:

• replace service curve with a generic "resource description" (that might consist of multiple parts such as min/max curves),
• add a resource descriptions to Link,
• add a resource descriptions to inPorts,
• add a resource descriptions to Flows, and
• add a resource descriptions to Turns

Having such a generic network model, we need to derive to the actual tool's one, of course. I can only comment on mapping to the DNC server graph used in the DiscoDNC. I.e., I assume all resources are given in terms of arrival and service curves (read from an external file https://github.com/NetCal/DiscoDNC/issues/9).

• Flows are shaped at their sources, this is a 1:1 mapping to the DNC model.
• Servers (assuming output queueing only) can then be created for
  • the output link's service curve (rate and (propagation) delay),
  • the outPort scheduler's service curves (for instance GPS might map to multiple DNC servers!),
  • the turn from input to output port's service curve (maximum delay)

I suppose the DiscoSNC would require a similar conversion. If so, this code should also reside in the network model's repository.

[matyesz]

See my answers below the questions with bold:

• You prefixed the ports according to their role with respect to the link connecting them, right? From my experience with the literature, I think they are better named according to their role within the device they belong to. I.e., I suggest renaming srcPort -> outPort and dstPort -> inPort to match output/input queueing assumptions.
  • Do we want a model with bidirectional links?

I would rather suggest txPort and rxPort (srcPort and dstPort can be the name for the attributes in the link). Bidirectional links can be handled with this model too. Actually Device->Ports will have all the ports and txPort or RxPort is just a reference to that port holding tx and rx attributes. For the same port you can have several references, so the model already supports bidirectional links too.

Path being able to store multicast is definitely a welcome addition. Here, theory is ahead of tool support. If I remember correctly, this 1:n-solution matches the idea of Bruno Cattelan. Let me try to get him involved. Actually flow will have a multicast feature as it can have several paths

Overall design Totally agree. We can use a resource description to hold curves or delays, if I remember well simple constant delays can also be modeled by curves, so is it not easier to model the connection inside the devices ports with static delay curves? In that way we would not use resource description but a Curve to represent any kind of delay (due to static delay or queuing...).

[matyesz]

Did some update based on comments:

[sbondorf]

Make outPort hold a Resource and it matches my point of view.

Delays can be modeled with a burst-delay curve that has an infinite burst after the delay. The conversion to the DNC server graph can easily take care to this, in a way transparent to the analysis.

I guess, if you wanted to model AFDX in very detail, you just need to replace the Device's simple turn model with a more sophisticated combination of components. I like that idea as it brings our modeling capabilities closer to the MPA RTC, yet, thanks to the conversions to the DNC server graph, we can still do an end-to-end delay analysis.

I also thought about generalizing link towards connecting multiple out/in ports -- like in a wireless medium. But I suggest postponing this for now.

[matyesz]

My idea/goal is to have a generic model that is able to handle all protocols. I will correct turns for device as it is a 0..1 connection (either ed or switch/gateway). Actually turns look like a port routing and filter so I will still polish that part.

BTW: could you please create the module for the model? At least we can move the actual model there...

[matyesz]

I have added the genreic turn model. Filtering is not represented (we can add it as a filter description to the resource) but it is a resource to enable delays and policiing. It references one path (thus a flow with multicasting) and one or several txPorts and several rxPorts where the path can be routed. IMO this representation can cover all of existing routing/gatewaying mechanism.

[matyesz]

Based on our last discussions the COM model can live without the links. We just need paths and turns if I understand well. We could introduce a physical model over the COM model that has links connecting ports.

[matyesz]

Can we agree on the model above, or do you have any suggestions? If agree, I can start implementing it.

[sbondorf]

At first sight, the model looks like a model for a device graph to me, right? Simply because there are no devices or ports in the server graphs that are automatically analyzed by the calculator. Or is it supposed to be an ultimately generic model that is used for both, device and server graphs? Phrased differently: Given this model, do you plan to have a mapping the server graph class or do you want to replace ServerGraph.java and adapt all DNC analysis algorithms to operate on the above model?

[matyesz]

My ultimate goal is the following: have a model that is easy to understand by users (automotive, aerospace...) and can be used also for calculations. Meeting with engineers from both I learned that they do not understand graphs just ports, switches and links so they will never be able to configure their own networks without these. To reach this we can follow the following paths:

1. We stay with the already existing model for calculations, introduce a new model for users and create a converter between the 2
2. We try to find a layered solution where conversion is easier and can be used for both reasons (like in AUTOSAR they have a physical/topology model, a comm model and a calculation model, that are extensions of each other.
3. We create a very generic model that supports everything in one (toughest task) After doing it on path 1 and trying also path 3 I think path 2 is the good way to go.

[matyesz]

Just to make clean: in netcal we must have a basic and extensible model for analysis via server graph. Upon that model we could build a project/ extension that could support comm networks with different protocols having their own service curves built from the config. As this is a different level of representation it must not be part of the existing project.

[sbondorf]

Yes, this is the best way in my opinion. Create a "modeling extension" that makes modeling for one domain (such as a communication standard) easy. Then transform this model into the server graph and run the (unchanged) analyses on it.

To give an example, assume output queuing only and priority scheduling with five priority classes in the above device graph model. Then, for conversion to a server graph, you would drop input ports and the turns but create five servers per output port. Only servers from the same priority class would be connected to each other (assuming flow priorities cannot change between devices). Flow routes need to be converted such that a flow only crosses servers of its priority class (where it interferes with other flows of its class) -- this is only trivial under the previous assumption of network-wide, static priorities. For the service curve, I'd assume that the output port in the above device graph model only has a single service curve and in oder to convert to five service curves for the individual servers in the server graph, you need to know the flows crossing this port, order them by priority and compute left-over service curves for the lower priority servers. I.e., this conversion is not just static and on the "topology level".

[matyesz]

Agreed, questions:

• is current server graph model able to support this approach
• do we want to have a common/simple model as a base for further domain specific models, or just leave the converters and model on future users?

[sbondorf]

The server graph is powerful enough for this approach -- in this case its very abstract nature is key and all the complexities need to be put into the converter. In fact, keeping the server graph at its tested bare minimum also means a converter needs to keep track of mappings from a device to the servers in the device etc. The algorithms running on the server graph do not assume anything in addition either. Operations needed from the server graph are trivial (mostly) and they are read-only (like getting subsequent servers, flows at some location etc.). The challenges will probably be to not end up with inconsistencies between device graph and server graph (e.g., due to feed-forwardizing the server graph), invalidating results when something changes in the device graph, etc.

Regarding the model, I think the RTC's "modular performance analysis" works quite well. I.e., having "building blocks" that can be combined. Then providing a sample combination to model for one domain would be solution the modeling solution I'd go for. Ideally, with more domains being modeled, more building blocks will be added to the tool. But as I am no domain expert for any domain, I do not know if this is possible (i.e., suitable for, say, AUTOSAR models). My assumption is based on the MPA RTC applications I have seen. Speaking highly of the MPA modeling approach, let me emphasize again that, on the other hand, their direct translation to min-plus-operations makes it hard (if not impossible) to apply modern network calculus analyses, let alone our implementations of them. But we can get all of them by converting to a server graph first.

[matyesz]

In this perhaos the title of the task is somehow outdated as it will not give modeling capabilities for existing solution bt create a new project for modeling a domain ad converting to server graph.

[matyesz]

The model has been implemented in ecore format according to above discussions. Enclosing project is NetCal/NetworkModel. The design was done by keeping extensibilty in firts place to be able to represent any protocol. Also there is a model converter under NetCal/DNC_NetworkModel_converter. See pull request: #83.

[davidalain]

I'm implementing the Ethernet standard as a layer above the DNC modules, and I was faced with many of @sbondorf and @matyesz topics discussed here:

1. How to model a standard (in my case the Ethernet) without changing the kernel of DNC?
2. How to convert traffic information to the arrival curve?
3. How to convert device resource to the service curve?

Some of my solutions are similar to those proposed by @matyesz.

For 2 and 3, I'm not sure how to do in the best and correct way.

For 1, I had to implement some classes of Ethernet specific context:

• EthernetInterface: an interface/port of Ethernet device with one input Server and one output Server
• EthernetDevice: generic representation of an Ethernet device
• EthernetEndSystem: an Ethernet device with only one interface
• EthernetSwitch: an Ethernet device with many interfaces and a switching fabric
• EthernetLink: a link with two ethernet interfaces
• EthernetInterfaceSpeedConfig: a factory of Curves based on interfaces' speed
• EthernetNetwork: a representation of ethernet network in a straightforward way to use

All of these implemented classes are in org.networkcalculus.dnc.standards.ethernet package in the ethernet_wrapper branch of my fork of DNC I have made two demos to run my implementation in some example Ethernet networks. They are in the package org.networkcalculus.dnc.standards.ethernet.demos.

But the critical point is do not change the kernel of DNC. I think it is not possible to make a more specific analysis of an Ethernet network with static priority and Time-Sensitive Networking (TSN) traffic shaping algorithms without change the kernel of DNC. Maybe I have to implement new classes (using inherit or even reimplement them) to run that analysis that I need.

For another point, I think that Ethernet standard modeling code I have made is going to the direction of NetCal/DNC_NetworkModel_converter project. It produces instances and uses only the DNC classes to run the analysis. It is like a converter.

[matyesz]

My idea is to have a simple but generic model representation for each network (Ethernet, AFDX, CAN...) that can be converted into DNC server graph. The common model is NetCal/NetworkModel project. If you generate the model code you will see that all of your model lements can be an extension of the generic model:

• EthernetInterfac ->port (input or outpout)
• EthernetDevic -> Device
• EthernetEndSystem -> an Ethernet device with only one interface
• EthernetSwitch -> an Ethernet device with many interfaces and a switching fabric
• EthernetLink-> Link
• EthernetInterfaceSpeedConfig -> perhaps flow
• EthernetNetwork -> network

According to above facts I would recommend to put your model in the NetCal/NetworkModel procejt extending the classes there and the existing converter will automatically convert it to server graph. Naturally you will need some new attributes and conversions to existing attributes in the generic model. At the moment I am working on the AFDX model that will give you a hint how to create your model. On DNC part: till you are able to model with arrival curves and service curves network calculus will be able to the calculations. At the moment generic model is using tokenbucket for calculations but that will change soon and the type of arrivalcurve will be coming from the network type. In my opinion you just need to create your arrival curve and service curve implementation (I think service curve in ethernet is the same curve based on the bandwidth). I can give you hany help needed to turn your ethernet model into an extension of the generic model I think this is the way we should move not writing millions of converters to millions of models.

[matyesz]

Please check branch https://github.com/NetCal/NetworkModel/tree/%231_Adding_ethernet_model in NetCal/NetworkModel. I added quickly the ethernet network elements. You can use that to develop your ethernet model. Unfortunatelly my time today is not enough now to complete it fully but will finish it soon, or you can use it and add your changes. Naturally you will have to add changes to the generic model in the uml format and regenerate the model.Or just ping mewith needed modifications and will add it. Hope this will help you in developing the ethernet model. I attach the generic model so you can see how to connect ethernet elements:

[matyesz]

Hello,

I solved it for afdx in network model converter without touching the dnc kernel.

BR, Zoltan

David Alain do Nascimento notifications@github.com ezt írta (időpont:

2019. aug. 14., Sze 22:29):

I'm implementing the Ethernet standard as a layer above the DNC modules, and I was faced with many of @sbondorf https://github.com/sbondorf and @matyesz https://github.com/matyesz topics discussed here:

1. How to model a standard (in my case the Ethernet) without changing the kernel of DNC?
2. How to convert traffic information to the arrival curve?
3. How to convert device resource to the service curve?

Some of my solutions are similar to those proposed by @matyesz https://github.com/matyesz.

For 2 and 3, I'm not sure how to do in the best and correct way.

For 1, I had to implement some classes of Ethernet specific context:

• EthernetInterface: an interface/port of Ethernet device with one input Server and one output Server
• EthernetDevice: generic representation of an Ethernet device
• EthernetEndSystem: an Ethernet device with only one interface
• EthernetSwitch: an Ethernet device with many interfaces and a switching fabric
• EthernetLink: a link with two ethernet interfaces
• EthernetInterfaceSpeedConfig: a factory of Curves based on interfaces' speed
• EthernetNetwork: a representation of ethernet network in a straightforward way to use

All of these implemented classes are in org.networkcalculus.dnc.standards.ethernet package in the ethernet_wrapper branch of my fork of DNC https://github.com/davidalain/DNC/commits/ethernet_wrapper I have made two demos to run my implementation in some example Ethernet networks. They are in the package org.networkcalculus.dnc.standards.ethernet.demos.

But the critical point is do not change the kernel of DNC. I think it is not possible to make a more specific analysis of an Ethernet network with static priority and Time-Sensitive Networking (TSN) traffic shaping algorithms without change the kernel of DNC. Maybe I have to implement new classes (using inherit or even reimplement them) to run that analysis that I need.

For another point, I think that Ethernet standard modeling code I have made is going to the direction of NetCal/DNC_NetworkModel_converter project. It produces instances and uses only the DNC classes to run the analysis. It is like a converter.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/NetCal/DNC/issues/8?email_source=notifications&email_token=ACTWVTS4H3REBTI5WD2ZQ7TQERTLJA5CNFSM4EY66S32YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD4KAONQ#issuecomment-521406262, or mute the thread https://github.com/notifications/unsubscribe-auth/ACTWVTRMHHYIRZIJW3RNV2TQERTLJANCNFSM4EY66S3Q .

[davidalain]

@matyesz Can you explain a little bit how did you do it?

[matyesz]

Hello,

briefly: each service class must have its own server on the same port so during conversion to DNC graph you can calculate the service curve for each server. I have pushed my code to network-converter project within DNC in a new branch, it is not merged yet.

BR, Zoltan

David Alain do Nascimento notifications@github.com ezt írta (időpont:

2019. okt. 13., Vas 5:51):

@matyesz https://github.com/matyesz Can you explain a little bit how did you do it?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/NetCal/DNC/issues/8?email_source=notifications&email_token=ACTWVTSFMI7BIJWWCUZCHLDQOKLM3A5CNFSM4EY66S32YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEBCNXII#issuecomment-541383585, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACTWVTXWOORFRVSLND6HTALQOKLM3ANCNFSM4EY66S3Q .