Directing two queue to one node

[arsiboo]

I'm encountering an issue in defining the q_args for 'num_servers' in case of connecting two queues to the same node. In my case each node has number of servers. Let's say two queues (labeled '2' and '3') arrive to the same node and the node's number of servers is '5'. Thus the 'num_servers' for queue '2' is set to '5', and 'num_servers' for queue '3' is set to '5'. But the thing is that I want both queues total 'num_servers' to be '5', not individually. Is this possible? How should I define the q_args in this case?

[djordon]

I think I understand what you're asking, but let me repeat it back to make sure that I got it.

Suppose we have a simple graph with three nodes named nodes 1, 2, and 3, where there is an edge from node 1 and 3, and from node 2 and 3. We want to have this network set up such that the total number of servers leading into node 3 is 5. So, if edge 1->3 has 4 agents being serviced, there can only be one agent being serviced on edge 2->3. Is this correct?

This isn't easy to do. If I were trying to do this, I'd subclass QueueServer and have this new class use a shared state. Here is a rough (and probably incorrect) sketch of what I'm thinking:

import queueing_tool as qt

class SharedQueueServer(qt.QueueServer):
    def __init__(self, shared_server_state: list[int], **kwargs):
        super().__init__(**kwargs)
        self.shared_server_state = shared_server_state
        self.total_num_servers = kwargs.get("num_servers", 1)

    @property
    def num_servers(self):
        return self.total_num_servers - self.shared_server_state[0]

    @num_servers.setter
    def num_servers(self, value):
        self.total_num_servers = value

    def next_event(self):
        next_event_type = self.next_event_description()
        # Event type 2 is a departure
        if next_event_type == 2:
            self.shared_server_state[0] += 1
            super().next_event(self)

        # Event type 1 is an arrival
        elif next_event_type == 1:
            self.shared_server_state[0] -= 1
            super().next_event(self)

# Make an adjacency list
adja_list = {0 : [2], 1: [2]}

# This says edges 0->2 and 1->2 will use the q_class with key 1
edge_type = {0: {2: 1}, 1: {2: 1}}

# Creates a networkx directed graph using the adjacency list and edge list
g = qt.adjacency2graph(adjacency=adja_list, edge_type=edge_type)

# Make a mapping between the edge types and the queue classes that sit on each
# edge. Do not use 0 as a key, it's used to map to NullQueues.
q_classes = {1: SharedQueueServer}

shared_state = [0]
q_args = {
    1: {'shared_server_state': shared_state, 'num_servers': 5},
}

qn = qt.QueueNetwork(g=g, q_classes=q_classes, q_args=q_args)

I'm not sure the above captures what you want, or if it even works! It seems tricky to get right. Moveover, even if the sketch above is correct, it won't actually work until I patch a bug related to the number of servers (which should ship this week). The bug is here https://github.com/djordon/queueing-tool/issues/64.

Anyway, hope this helps!

[arsiboo]

Thanks a lot for a very quick reply and tip. Then I will wait for the update.

[arsiboo]

Hi,

I saw you merged it but I don't know how to get the latest version. I usually use pip to install packages.

[djordon]

I haven't cut the release yet. I'm still on track to ship that fix and one or two other changes this week. I'll post here when I do.

[arsiboo]

Thank you

[djordon]

@arsiboo the new version of queueing-tool has been published.

[arsiboo]

Thanks again.

[arsiboo]

I tried to use the SharedQueueServer and I encountered an error in simulation time when running the simulation:

"TypeError: 'int' object is not subscriptable"

[djordon]

I'm not sure how you got that error. I just ran the code I posted above and got a different error (I forgot to return the agent when there was a departure). After fixing that error and plugging a couple of lingering logic bugs I think it works as intended.

Specifically, I got the sign wrong for how to update the shared state when there was an arrival or a departure, I updated on arrivals too frequently, I didn't return the departure, and I called super().next_event incorrectly. Here is the diff:

@@ -19,13 +19,15 @@ class SharedQueueServer(qt.QueueServer):
         next_event_type = self.next_event_description()
         # Event type 2 is a departure
         if next_event_type == 2:
-            self.shared_server_state[0] += 1
-            super().next_event(self)
+            self.shared_server_state[0] -= 1
+            return super().next_event()

         # Event type 1 is an arrival
         elif next_event_type == 1:
-            self.shared_server_state[0] -= 1
-            super().next_event(self)
+            if self.num_system - len(self.queue) < self.num_servers:
+                self.shared_server_state[0] += 1
+            super().next_event()

 # Make an adjacency list

Here is the updated code

import queueing_tool as qt

class SharedQueueServer(qt.QueueServer):
    def __init__(self, shared_server_state: list[int], **kwargs):
        super().__init__(**kwargs)
        self.shared_server_state = shared_server_state
        self.total_num_servers = kwargs.get("num_servers", 1)

    @property
    def num_servers(self):
        return self.total_num_servers - self.shared_server_state[0]

    @num_servers.setter
    def num_servers(self, value):
        self.total_num_servers = value

    def next_event(self):
        next_event_type = self.next_event_description()
        # Event type 2 is a departure
        if next_event_type == 2:
            self.shared_server_state[0] -= 1
            return super().next_event()

        # Event type 1 is an arrival
        elif next_event_type == 1:
            # We only use a server if there is capacity.
            if self.num_system - len(self.queue) < self.num_servers:
                self.shared_server_state[0] += 1
            super().next_event()

# Make an adjacency list
adja_list = {0 : [2], 1: [2]}

# This says edges 0->2 and 1->2 will use the q_class with key 1
edge_type = {0: {2: 1}, 1: {2: 1}}

# Creates a networkx directed graph using the adjacency list and edge list
g = qt.adjacency2graph(adjacency=adja_list, edge_type=edge_type)

# Make a mapping between the edge types and the queue classes that sit on each
# edge. Do not use 0 as a key, it's used to map to NullQueues.
q_classes = {1: SharedQueueServer}

shared_state = [0]
q_args = {
    1: {'shared_server_state': shared_state, 'num_servers': 5},
}

qn = qt.QueueNetwork(g=g, q_classes=q_classes, q_args=q_args)

Hopefully this works as you intended.

[arsiboo]

It works fine. Thanks.

[djordon]

What code did you run?

On Mon, Oct 10, 2022, 8:12 AM m1karmida @.***> wrote:

I tried to use the SharedQueueServer and I encountered an error in simulation time when running the simulation:

"TypeError: 'int' object is not subscriptable"

Hi, I also needed to use the same code for drawing my queueuing network, but i occured in the same error. How do you fixed it?

— Reply to this email directly, view it on GitHub https://github.com/djordon/queueing-tool/issues/76#issuecomment-1273221233, or unsubscribe https://github.com/notifications/unsubscribe-auth/AB534UC42NSYHYDOHYRP7KTWCQB2HANCNFSM6AAAAAAQ36UTZE . You are receiving this because you commented.Message ID: @.***>

[arsiboo]

The class that you built here but with my network as an input.

[djordon]

The class that you built here but with my network as an input.

Would you mind posting a stacktrace of the exception, so that I can see where you hit the error?

[arsiboo]

The error was showing on the class when you first introduced the code, not the edited one. Just to make sure I understood you correctly, you want to see the error and the code which produces the error right?

[djordon]

Ohhh whoops I misunderstood. I saw this on my phone and thought there was a new error that my new code didn't address. Never mind!

[ayanchak1508]

Hi, sorry to bother you about an old issue, but this example does not work when the number of servers in a shared queue is 1. I would assume that what happens is that the server services one queue at a time, but what ends up happening is that all the queues get blocked. I think there may be a deadlock happening somewhere in the code.

[djordon]

Oh that doesn't sound good. Did you run exactly what I had in https://github.com/djordon/queueing-tool/issues/76#issuecomment-1272452674 except you had the following changed

q_args = {
-    1: {'shared_server_state': shared_state, 'num_servers': 5},
+    1: {'shared_server_state': shared_state, 'num_servers': 1},
}

? If so, what where you seeing that made you think that there was deadlocking?

[ayanchak1508]

Hi, sorry for the late reply, but yes I made the change you mentioned and added some lines for simulating and diagnosing the issue:

qn.start_collecting_data()
qn.initialize(edge_type=1)
qn.simulate(t=1000)
agent_data = qn.get_agent_data(edge_type=1)
for key in agent_data.keys():
    t_entry, t_exit = agent_data[key][0][0], agent_data[key][0][2]
    print(f"Agent {key} entered at {t_entry} and exited at {t_exit}")

For the case of num_servers = 5, it outputs:

Agent (0, 0) entered at 2.3704631666894906 and exited at 2.5751294027555196
Agent (0, 1) entered at 3.265481736476013 and exited at 3.5419208610912234
...

which tells me that the agents are entering and exiting the system normally.

However, for the case of num_servers = 1, it outputs:

Agent (0, 0) entered at 1.596414009818101 and exited at 0.0
Agent (0, 1) entered at 1.6759622096507019 and exited at 0.0
...

All of the agents have an exit time of 0.0. Hence, I infer that the agents never leave the system, and the single server node is somehow caught in a deadlock unable to service agents from either queue.

I also animated the network for num_servers = 1, and the figure is stuck here: The dark edges indicate that the queues have a high load. For the case of num_servers = 5, the edges are much lighter and continuously flicker, indicating agents entering and leaving those queues.

Additionally, the output of qn.num_events is fixed at 1000 for the case of num_servers = 1 no matter how long I simulate, whereas the output of qn.num_events increases proportionally with time for the case of num_servers = 5. (I guess there is some limit in the source code preventing new agents from entering queues from the outside in the case of severe back pressure?)

I also checked with:

q_args = {
-    1: {'shared_server_state': shared_state, 'num_servers': 5},
+    1: {'shared_server_state': shared_state, 'num_servers': 1, 'service_f': lambda t: t},
}

to make sure the service time was not the bottleneck. and I have the same observations.

[djordon]

Sorry for the delay here. Yeah, this looks bad, let me take a deeper look here to see.

[djordon]

So yeah we essentially had a "deadlock" in my above example code. No agents were being serviced after the first one. This was because I did not update the QueueServer shared state correctly. I also found an issue with how I handled departures.

But I think I fixed this example with the following:

import queueing_tool as qt

class SharedQueueServer(qt.QueueServer):
    def __init__(self, shared_server_state: list[int], **kwargs):
        super().__init__(**kwargs)
        self.shared_server_state = shared_server_state
        self.total_num_servers = kwargs.get("num_servers", 1)

    @property
    def num_servers(self):
        return self.total_num_servers - self.shared_server_state[0]

    @num_servers.setter
    def num_servers(self, value):
        self.total_num_servers = value

    def next_event(self):
        next_event_type = self.next_event_description()

        # Event type 2 is a departure
        if next_event_type == 2:
            # we need to record the server state and reset it to make
            # sure things work during the call to super().next_event()
            num_queued = len(self.queue)
            shared_server_state = self.shared_server_state[0]
            self.shared_server_state[0] = 0

            departure = super().next_event()

            # Now restore the previous shared state, and update it if we
            # didn't replace the departure with an agent from the queue
            self.shared_server_state[0] = shared_server_state
            if num_queued == 0:
                self.shared_server_state[0] -= 1

            return departure

        # Event type 1 is an arrival
        elif next_event_type == 1:
            super().next_event()
            # We only use a server if there was capacity.
            if self.num_system <= self.num_servers:
                self.shared_server_state[0] += 1

# Make an adjacency list
adja_list = {0 : [2], 1: [2]}

# This says edges 0->2 and 1->2 will use the q_class with key 1
edge_type = {0: {2: 1}, 1: {2: 1}}

# Creates a networkx directed graph using the adjacency list and edge list
g = qt.adjacency2graph(adjacency=adja_list, edge_type=edge_type)

# Make a mapping between the edge types and the queue classes that sit on each
# edge. Do not use 0 as a key, it's used to map to NullQueues.
q_classes = {1: SharedQueueServer}

shared_state = [0]
q_args = {
    1: {'shared_server_state': shared_state, 'num_servers': 5},
}

qn = qt.QueueNetwork(g=g, q_classes=q_classes, q_args=q_args)
qn.start_collecting_data()
qn.initialize(edge_type=1)
qn.simulate(t=200)

Now for some more details about the issues with the original code.

1. I did not correctly handle the case where agents were in the queue for the server at the time of departure. With the above code, when there is a departure and the QueueServer has agents waiting in the queue, I explicitly take someone from the queue and place them in the server. When this happens I do not update the shared state since there was essentially no change.
2. I did not correctly account for the shared state on arrival of an agent. With the above code I update the shared state in the correct order on arrival.

Well shared state was tricky. I hope this fixes it.

[ayanchak1508]

Hi! Thank you very much for fixing the code quickly. It seems to be working correctly now.

(P.S. Really sorry for not taking a look before and for my very late reply, I was caught up with some other things. Thanks again!)