Hi all, I have a simulation problem.

A phone line connecting 2 cities only operates from 8AM to 12AM (16 hours) everyday. Customers in these 2 cities randomly make phone calls through it. The distribution for the time interval between 2 calls is approximately an exponential function with lamda = 1/6 minutes^(-1). The distribution for the time each phone call lasts is approximately N(6,4) in minutes. When the line is busy, the next customer just gives up making his/her phone call. Write a program to simulate the phone line problem when there are n phone lines. (n is an arbitrary integer).

I know the algorithm to simulate 1 phone line, but am lost when it comes to a variable number of phone lines. All I can think of is to keep track of the time when a call ends that is the earliest of all the phone lines, and the next call is made to that phone line.

However, after updating that line, if another call comes in, I won't be able to find the phone line for that call to connect to without going through all the phone lines and comparing the times. This is going to be a big problem is there are thousands of phone lines.

Can someone please help me?

Thank you.

Regards,
Rayne

There are more subscribers than trunks. Any time a subscriber wants to make a call, he is connected to whatever trunk is available at that time.

To simulate a system with one trunk and more than one subscriber, you only need one variable to indicate whether a trunk is free. When a call request comes in, if the trunk is free, you assign the termination time to that variable.
If the time of the next request is greater than or equal to the time that you previously stored, the line is available (and the new termination time is stored). If the next request occurs at a time less than the time stored in the variable, the request is denied.


For n trunks, the simulation procedure can be the same, except that you have n variables to keep track of the n lines. (Sounds like an array, right?)

Here is a simple way that I could see to implement the simulation:

As I see it, you have a table (array) of n lines; initially they are not busy. (Initial to all zeros.) Each table entry will hold the ending time of a call in progress on that line.

You have a counter, say, CallsDenied, to keep track of the number of requests that were not honored. (Intitiaze to zero.)

You have some way of indicating simulation time, say a variable named CurrentTime. It starts at zero.

Here's the way I can see the simulation (as "easy" as 1-2-3):

Repeat steps 1-3 while the simulation time is less than some assigned limit:

1. Generate a call request from the exponential distribution. The time of the request becomes the new simulation time.

2. When a call request comes in: Look through the table for an available line. If a line is available, place the time that the line will be released in the table entry for that line. This value is
(Current simulation time) + (Time returned from the call duration statistical distribution.)

3. If no lines are available, the caller gets a "fast busy" signal, indicating that the call cannot be completed (Add '1' to your CallsDenied counter.)

Now how do you determine whether a line is available? Well, if the current simulation time is greater than or equal to the table entry for a given line, that call has been completed, so the line is available.



You say "This is going to be a big problem if there are thousands of lines". I think that the expression "big problem" is kind of subjective. How much computer time do you think it would take to simulate an hour's real time for a given traffic pattern for a central office with 100 subscribers and 10 trunks? How about 1000 subscribers and 10 trunks? How about 10000 subscribers and 100 trunks? How about 100000 subscribers and 1000 trunks? Try it and see. (Pick your own numbers and traffic statistics.)

(What if the traffic pattern changes every hour? That is, the parameter of the request arrival distribution changes as businesses open and close at particular times during the day. What about changes for holidays --- Everybody calls Mom on Mother's day. How many trunks do you need to keep from denying more than 1 percent of call requests on Christmas? Now, you are getting into "big problems", due to the complications in getting the statical parameters to simulate worst-case calling patterns. Simulation techniques and implementations, however, remain the same.)

Regards,

Dave

However, in this case, n is unknown, so how do I implement the array? I have a plot a graph at the end of the program to show the rate of failure against n, which means I have to vary the value of n in the same program. Do I use dynamic memory allocation?

Thank you.

Regards,
Rayne

Sounds to me that you need either
1) an array of N connections that keep the current state of each line (in_use=1 or free=0)
2) a variable (maybe nconnect) that keeps track of the number of connections currently in use.

It's not that big a problem to compare thousands of lines for a computer. They're fast!

__________________

Got a cough? Go home tonight and eat a whole box of Ex-Lax. Tomorrow, you'll be afraid to cough.
-- Pearl Williams

If it's C, you can use use malloc()-free(). (Each new value of n gets a new array, which is free()ed before the next n is used.) This would work in C or C++.

If it's C++, you can consider using a Standard Template Library vector or list or something. This method might be more easily extended to future more complex or larger-scale simulation methods.

By the way, the simple way that I outlined is not necessarily the "best" way, but I think it suffices for the problem that you stated. General purpose simulations can be implemented lots of ways (time-driven, event-driven, etc.)
They may involve event tables sorted by time and lots of other things that you don't necessarily need for the simple case here.

Regards,

Dave

It's not either/or.

Since calls have different durations, and there may be n calls in progress at a given time, you have to keep track of all of them. One way is to do what I said. Another way is make an event list that holds termination times for calls in progress. The number of events in the list at any given time is equal to the number of trunks in use (so you don't actually need an array of trunks). Since the maximum size of the event list is equal to the number of trunks, I don't see any advantage (but it's certainly a possible way of doing it).

If you are using a C++ STL set for the event table, then entries are automatically sorted as they are entered, and the member function size() keeps track (efficiently, I think) of the number of entries at a given time. Then items are removed from the list as simulation time reaches the time of the first item. This is kind of the way that some real bigtime simulation programs are implemented.

However, for people just learning implementation of simulations like this, I think it's more instructive to deal with simple things, like arrays in C (even if they are writing in C++ --- unless an instructor wants them to use certain language features like STL lists etc.)

I repeat that I don't necessarily think that what I showed is the "best" way; it's certainly not the only way, but it is, I think, a way. If you see a way that makes more sense to you, I hope you try it. Yes, try it.

My point is that, if you see a way that you like more than the steps that I outlined: go for it. Try it. See if it gives reasonable results.

Here's my approach to learning things like this:

Make sure you understand the principles of simulation first. Get your feet wet by running some simulations for which you can compare "known" results (using queueing theory or other stochastic methods, maybe). Then dive right in and try more efficient ways of doing really large simulation problems (if you are still conscious, and if you haven't decided to change your career to gardening or something).

Regards,

Dave

Not really. You need to keep track of each line that has a call. You can only have as many calls as lines. If all lines are full, no more calls. Therefore, you keep track of each line and whether or not there is a free line when the next call is placed.

__________________

Got a cough? Go home tonight and eat a whole box of Ex-Lax. Tomorrow, you'll be afraid to cough.
-- Pearl Williams

In my first post I suggested an array of n lines. The table entry for each line is the termination time for a call assigned to that line (all are initialized to zero). When a call request is generated, the termination time for that call is placed in the table entry of an idle line. When simulation time becomes greater than or equal to the termination time, that line is idle again. It's not enough just to mark the line idle or busy; it must become idle again after a given call is terminated.

The other way that I suggested merely has a list of termination times (for this simulation, it really doesn't matter what line each call is assigned). The maximum size of this list is also n, since there can be no more than n calls active. This is a more general method, since many problems have more than one kind of event, and the event list holds information not only for the time of the event, but the nature of the event as well. People studying simulation methods will encounter this and other techniques.

There may or may not be implementation advantages to one method or the other (or to one of numerous other methods).

Regards,

Dave