It is often nice to be able to simulate a queue or stack discipline for places, e.g. for communication over a TCP channel.

Alas, CPN Tools does not currently support this, but this is easy done by the modeler.

Example

This is a very simple model of a sender and a receiver.

The sender, sends packages onto a network.

The receiver receives packages from the network.

Stack

We want the network to have a LIFO (last in, first out), or stack behavior. (Yes, this is not realistic, but then I only need to introduce one example).

We change the type of the place from T to list T, and make all ingoing arcs preprend to the list, and all outgoing arcs should then remove the head from the list.

When I do this to the above example, I get:

Changes to declarations

  • I have added a new type PACKAGEs of type list PACKAGE
  • I have added a new variable of the new type PACKAGEs

Changes to the network place

  • I change the type from PACKAGE to PACKAGEs
  • I add/change the initial marking to be a list. In this case the original initial marking was the empty marking, and I add the empty list []. If the original marking had been, e.g., 1`1++2`4, I could have changed it to, e.g., [1,4,1] (the ordering DOES matter now).

Changes to (ingoing and outgoing) arcs

  • I change the inscription of the arc from p to p::ps, where ps is the new variable of the new type PACKAGEs
  • I add a new arc in the opposite direction with the inscription ps

Queues

We want the network to have a FIFO (first in, first out), or queue behavior. This is like the behavior of TCP streams.

We change the type of the place from T to list T, and make all ingoing arcs append to the list, and all outgoing arcs should then remove the head from the list.

The only difference from stacks is that instead of prepending to the list, we append to it. When I do this to the example, I obtain:

Changes to declarations

  • I have added a new type PACKAGEs of type list PACKAGE
  • I have added a new variable of the new type PACKAGEs

 Changes to the network place

  • I change the type from PACKAGE to PACKAGEs
  • I add/change the initial marking to be a list. In this case the original initial marking was the empty marking, and I add the empty list []. If the original marking had been, e.g., 1`1++2`4, I could have changed it to, e.g., [1, 4, 1] (the ordering DOES matter now).

Changes to outgoing arcs

  • I change the inscription of the arc from p to p::ps, where ps is the new variable of the new type PACKAGEs
  • I add a new arc in the opposite direction with the inscription ps

Changes to incoming arcs

  • I change the inscription of the arc from p to ps^^[p], where ps is the new variable of the new type PACKAGEs
  • I add a new arc in the opposite direction with the inscription ps

Priority queues

We want the network to have a priority-queue behavior, i.e. the priority of a packet determines the order in which it is handled. This is similar to IP quality-of-service options which allow datagrams to be identified (and possibly handled) with eight levels of precedence.

We change the type of the place from T to list T, and make all ingoing arcs insert elements into the list according to precedence/priority, and all outgoing arcs should then remove the head from the list.

The difference from FIFO queues is that instead of appending to the list, elements are added according to their priority. When I do this to the example, I obtain:

Changes to declarations

  • I have added a new type PACKAGEs of type list PACKAGE
  • I have added a new variable of the new type PACKAGEs
  • I add a function higherPriority to determine whether one package has higher priority than another
  • I add a function pinsert for inserting packages into a list according to their priority

Changes to the network place

  • I change the type from PACKAGE to PACKAGEs
  • I add/change the initial marking to be a list. In this case the original initial marking was the empty marking, and I add the empty list []. If the original marking had been, e.g., 1`1++2`4, I could have changed it to, e.g., [4, 1, 1] (the ordering DOES matter now).

Changes to outgoing arcs

  • I change the inscription of the arc from p to p::ps, where ps is the new variable of the new type PACKAGEs
  • I add a new arc in the opposite direction with the inscription ps

Changes to ingoing arcs

  • I change the inscription of the arc from p to pinsert p ps, where ps is the new variable of the new type PACKAGEs
  • I add a new arc in the opposite direction with the inscription ps

Examples

The examples described in this document can be downloaded

Inhibitor arcs
Graphical feedback

You must be logged in to post a comment.