Queues and stacks

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.

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.

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:

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

• 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).

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

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:

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

• 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).

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

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

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:

• 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

• 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).

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

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

The examples described in this document can be downloaded

• the original example with no ordering on the network
• the example where the network has a LIFO or stack semantics
• the example where the network has a FIFO or queue semantics
• the example where the network has priority queue semantics