One of our researchers here at WHOI is building a new system to allow
multiple vessels to dial up a shore station (using Iridium modems) to
deliver data files. The shore station is planned to have a single
modem. I was curious just how many callers we can expect to service on
a single modem without formal scheduling, given that they make calls
with varying frequency and for varying durations.
I haven't been given any actual figures for frequency and duration, so I
can't actually do the math for it yet. But it seemed like a moderately
interesting problem, so I tossed together a really cheap & primitive
simulation using CLOS objects to represent callers with different
requirements.
In the hope that some fellow Lisp-newbie might find it interesting, here
it is:
; Primitive sim for callers to a modem
(defvar *TIME* 0)
(defvar *BUSY-TIME* 0)
(defvar *CALLERS* nil)
(defclass caller ()
((name :type string :accessor name :initarg :name)
(duration :type integer :accessor duration :initarg :duration)))
(defclass regular-caller (caller)
((interval :type integer :accessor interval :initarg :interval)
(counter :type integer :accessor counter :initarg :counter :initform 1)))
(defclass irregular-caller (regular-caller)
((deviation :type integer :accessor deviation :initarg :deviation)))
(defmethod tick ((caller caller))
"You can tick a plain caller, buut it will never call."
(declare (ignore caller))
nil)
(defmethod tick ((caller regular-caller))
"Increment the counter. If it equals the interval, call."
(when (= (decf (counter caller)) 0)
(setf (counter caller) (interval caller))
(call caller)))
(defmethod tick ((caller irregular-caller))
"Just like a regular-caller, but perturbed a little."
(when (= (decf (counter caller)) 0)
(setf (counter caller)
(+ (interval caller)
(- (random (* 2 (deviation caller))) (deviation caller))))
(call caller)))
(defmethod tick ((list list))
(mapc #'tick list))
(defmethod call ((caller caller))
"Try to place a call, displaying success or busy."
(if (= *BUSY-TIME* 0)
(progn
(format t "~%~5D CALL SUCCEEDS for ~A" *TIME* (name caller))
(setf *BUSY-TIME* (duration caller)))
(progn
(format t "~%~5D BUSY SIGNAL for ~A" *TIME* (name caller)))))
(defmethod call :after ((caller regular-caller))
"Display the time to the next call attempt."
(format t "~40,5T (Next in ~D ticks)" (counter caller)))
(defun clock-tick ()
"Do one clock tick."
(incf *TIME*)
(when (/= *BUSY-TIME* 0) (decf *BUSY-TIME*))
(tick *CALLERS*))
(defun new-callers (&rest callers)
(mapc #'(lambda (x) (push x *CALLERS*)) callers))
(new-callers
(make-instance 'irregular-caller :name "Hourly"
:duration 5 :interval 60 :deviation 5 :counter 1)
(make-instance 'irregular-caller :name "Lag Hourly"
:duration 5 :interval 60 :deviation 5 :counter 2)
(make-instance 'irregular-caller :name "Speedy"
:duration 1 :interval 10 :deviation 5 :counter 3)
(make-instance 'irregular-caller :name "Dopey"
:duration 2 :interval 20 :deviation 10 :counter 4)
(make-instance 'irregular-caller :name "Plod"
:duration 10 :interval 80 :deviation 10 :counter 5))
(defun n-ticks (n)
(loop for click below n
do (clock-tick)))
(n-ticks 400)
--
Karl A. Krueger <········@example.edu> { s/example/whoi/ }
Every program has at least one bug and can be shortened by at least one line.
By induction, every program can be reduced to one line which does not work.
On Thu, 4 Nov 2004 01:56:36 +0000 (UTC), <········@example.edu> wrote:
> One of our researchers here at WHOI is building a new system to allow
> multiple vessels to dial up a shore station (using Iridium modems) to
> deliver data files. The shore station is planned to have a single
> modem. I was curious just how many callers we can expect to service on
> a single modem without formal scheduling, given that they make calls
> with varying frequency and for varying durations.
That's very similar to an old packet radio problem. As I recall, it
was the ALOHA system in Hawaii about 30 years ago. There may be
results of interest someplace on the internet, as packet radio is
still around.
--
Brownian motion is correctly colored.
"Karl A. Krueger" <········@example.edu> wrote in message
·················@baldur.whoi.edu...
> One of our researchers here at WHOI is building a new system to allow
> multiple vessels to dial up a shore station (using Iridium modems) to
> deliver data files. The shore station is planned to have a single
> modem. I was curious just how many callers we can expect to service on
> a single modem without formal scheduling, given that they make calls
> with varying frequency and for varying durations.
> --
> Karl A. Krueger <········@example.edu> { s/example/whoi/ }
>
Nice job. In fact if you can embellish it a little further, it can become
useful even as an exercise or as a small case study in a Lisp tutorial
book,class, or online.
Your problem has not so much to do with what the other responder alluded to
(i.e. context reminiscent of the ALOHA packet network) as the only thing in
common is the aspect of collision and random-time retraction before
initiating the attempt. The principle of collision avoidance is inherent in
every shared (and non policed) medium like e.g..Ethernet, and even in WiFi
channels in IEEE802.11 schemes. Your problem as you correctly stated is the
lack of convincing numbers, which implies a lack of knowledge of the
underlying statistics (frequency of calls and duration). Maybe I can help
you.
Having been there and done the same thing but on a military application, if
you want to try realistic numbers, I propose that you consider the fact that
there are 2 quasi-unrelated factors you have to make assumptions for: (i)
statistical distribution of call arrivals and (ii) statistical distribution
of holding times (by callers). In digital telephony the former is a
classical case of Poisson distribution, while the second can be split into
two cases (a) one where all calls have a constant holding time and (b) an
exponential holding time. I say quasi-unrelated because life shows they are
not. Assuming they are however gives you some surprisingly good predictors.
Although constant holding times cannot be assumed for classical phone voice
conversations, one usually assumes this constraint for such activities as
per-call call-processing requirements, inter-site address signaling,
applicable operator assistance, and even recorded message playback when
callers just call to receive say instructions or a weather bulletin update.
It is also useful in fixed packet length networks but that may not be
applicable to your case. Regarding the exponential holding time distribution
this is a striking observation from real life that the statistics of voice
conversations exhibit a tremendous resemblance to the exponential
distribution, where one essentially plots over time t the probability that a
specific call's holding time will exceeds a specific value t .
If you are interested in the specific formulas and you cannot find them
easily, feel free to drop me an e-mail and I will be send them to you
separately, without us bogging down the whole forum.
Panos
Panos C. Lekkas
·······@ieee.org
In article <···············@corp.supernews.com>,
"xstream" <·······@attglobal.net> wrote:
[interesting information snipped.]
> If you are interested in the specific formulas and you cannot find them
> easily, feel free to drop me an e-mail and I will be send them to you
> separately, without us bogging down the whole forum.
C'mon, you can't tease us like that and withold the details!
"Sashank Varma" <····@vanderbilt.edu> wrote in message
·······························@news.vanderbilt.edu...
> In article <···············@corp.supernews.com>,
> "xstream" <·······@attglobal.net> wrote:
>
> C'mon, you can't tease us like that and withold the details!
Do you want me to write down wholesale probability distribution functions?
Try any standard text in the telephony traffic theory area, like e.g.
DIGITAL TELEPHONY 2nd Ed., by John Bellamy. You library must have it. These
functions are clearly spelled out in there under Erlang traffic loads, etc.
Hope this helps.
Panos C. Lekkas
xstream <·······@attglobal.net> wrote:
> Your problem has not so much to do with what the other responder
> alluded to (i.e. context reminiscent of the ALOHA packet network) as
> the only thing in common is the aspect of collision and random-time
> retraction before initiating the attempt. The principle of collision
> avoidance is inherent in every shared (and non policed) medium like
> e.g..Ethernet, and even in WiFi channels in IEEE802.11 schemes.
Well, there's a big difference between Ethernets and phone systems like
this: on a (classic, shared-media) Ethernet, if two stations transmit
"at the same time", they get a collision and -both- frames are wasted.
On a modem, if two stations call in at the same time, one of those calls
is going to be completed and answered, and the other is going to get a
busy signal.
This changes the game theory of it. On an Ethernet, it's not in the
interest of each station to simply retransmit as fast as possible,
because all that would accomplish is to fill the medium with collision
and let nobody's frames through. On a phone system, it's arguably just
fine behavior to keep redialing (at a moderate pace) until you get in --
in the very manner that terminal software like Telix used to do to get
into single-line BBSes.
The problem then is ensuring that each station gets some chance to dial
in -- and that's where redialing as fast as you can isn't OK. I don't
think we're going to be able to escape scheduling for that if the number
of stations is great enough. I certainly remember from the BBS days
that redialing as fast as you can is -no- guarantee you're going to get
on to any particular board in any amount of time ... :)
> Your problem as you correctly stated is the lack of convincing
> numbers, which implies a lack of knowledge of the underlying
> statistics (frequency of calls and duration). Maybe I can help you.
Thanks for your suggestions -- once I have some reasonable numbers I
certainly will be digging into the math of it more. Even if it does not
turn out to be a serious issue for this system, it's certainly an
interesting problem.
--
Karl A. Krueger <········@example.edu> { s/example/whoi/ }
Every program has at least one bug and can be shortened by at least one line.
By induction, every program can be reduced to one line which does not work.
"Karl A. Krueger" <········@example.edu> wrote in message
················@baldur.whoi.edu...
> xstream <·······@attglobal.net> wrote:
> On a modem, if two stations call in at the same time, one of those calls
> is going to be completed and answered, and the other is going to get a
> busy signal.
>
> This changes the game theory of it.
> The problem then is ensuring that each station gets some chance to dial
> in -- and that's where redialing as fast as you can isn't OK. I don't
> think we're going to be able to escape scheduling for that if the number
> of stations is great enough. I certainly remember from the BBS days
> that redialing as fast as you can is -no- guarantee you're going to get
> on to any particular board in any amount of time ... :)
>
> > Thanks for your suggestions -- once I have some reasonable numbers I
> certainly will be digging into the math of it more. Even if it does not
> turn out to be a serious issue for this system, it's certainly an
> interesting problem.
>
I agree with you.
Incidentally, and you are probably already aware of this, the probability
distribution function that describes the behavior of the values of the
'random' amount of time taken when someone waits to redial, depends on the
implementation of the underlying RNG generator and its statistical
robustness. I have seen many skewed implementations that give at first sight
a false impression of randomness, yet things turn out to be on occasions
quite predictable (in those ill-formulated implementations). You may want to
keep an eye on how your system actually produces these random numbers. For
large numbers of callers you may find a surprise.
Also, if you end up looking into scheduling, you will be inevitably
confronted with a dilemma on the issue of "fairness", which is not
objectively definable in one way only. I am sure you must be looking into
this as well. In other words, what is fair, and how fair can you be with
everyone? This is a large area in network theory with tons of references
and multiple algorithms with numerous trade-offs. I am sure you are aware of
these things!
Good luck!
Panos C. Lekkas
·······@ieee.org
xstream <·······@attglobal.net> wrote:
> Incidentally, and you are probably already aware of this, the probability
> distribution function that describes the behavior of the values of the
> 'random' amount of time taken when someone waits to redial, depends on the
> implementation of the underlying RNG generator and its statistical
> robustness. I have seen many skewed implementations that give at first sight
> a false impression of randomness, yet things turn out to be on occasions
> quite predictable (in those ill-formulated implementations). You may want to
> keep an eye on how your system actually produces these random numbers. For
> large numbers of callers you may find a surprise.
When I was in the 8th grade or so, I was delighted to find a freeware
DOS structured-BASIC compiler -- hey wow, I can write BASIC and compile
to standalone .COM files! And it even supports graphics!
I promptly wrote a quick graphical demo of a random walk, using the
built-in "random number generator" ... and discovered for myself, with
-no- background in pseudorandom number generation, the ridiculously
small periodicity of that PRNG.
(The fact that the random-walk demo kept drawing the same little doodle
over and over again, slightly offset diagonally, rather gave it away.)
Again, not knowing anything about PRNGs, I set about trying to find ways
to improve it -- for instance, reseeding it (at pseudorandom intervals)
from the milliseconds counter in the system timer. This did indeed keep
my doodle generator interesting for a longer time ... but eventually
this too got in a rut and started repeatedly drawing a little thingie
that sort of looked like the state of Kentucky.
My conclusion at the time was that the compiler simply had a buggy
"random number generator".
I was much enlightened, later on, to discover Knuth's famous quote about
algorithmic "random numbers" and a state of sin. :)
--
Karl A. Krueger <········@example.edu> { s/example/whoi/ }
Every program has at least one bug and can be shortened by at least one line.
By induction, every program can be reduced to one line which does not work.
Karl A. Krueger wrote:
> One of our researchers here at WHOI is building a new system to allow
> multiple vessels to dial up a shore station (using Iridium modems) to
> deliver data files. The shore station is planned to have a single
> modem. I was curious just how many callers we can expect to service on
> a single modem without formal scheduling, given that they make calls
> with varying frequency and for varying durations.
>
> I haven't been given any actual figures for frequency and duration, so I
> can't actually do the math for it yet. But it seemed like a moderately
> interesting problem, so I tossed together a really cheap & primitive
> simulation using CLOS objects to represent callers with different
> requirements.
>
This is interesting....
I've been considering a packet-radio peer-to-peer
local-information sharing application for boaters as
a possible thing to develop.
All of these guys have electronic charts and GPS. But
often the charts are outdated or wrong, so they also
have to have instruments: Everything from depthsounders
to weather indicators. And despite advances, internet
connectivity on the water tends to be low-bandwidth,
expensive, spotty, and unreliable, especially far from
shore or in pristine parts of the world that are far
from overdevelopment. Boat-to-boat contacts can be
had in many situations where shore stations can't reach
or in areas of the world where shore stations are not
installed, and radio waves are more-or-less free.
What I was thinking is that there's maybe a niche for
a boat-to-boat network, where the instrument readings
get shared around automatically for all the boaters
who have the appliance. I was thinking of using VHS
or 900MHz frequencies, which are effectively line-of-sight;
The result being that if there's another boat around that
has the appliance, your nav station *knows* about the
coral heads up there that have grown since the chart
was made, or the sandbar that's built up, or the
anchorage that's been dredged or gotten mooring bouys
or whatever since last time the electronic charts got
updated, or the depthsounder readings where the
charts are just plain wrong, etc. Even local information
like the new ship channel that small boats have to stay
clear of or where the internet cafe's, good restaurants,
marinas and laundromats are in the local port town if
someone who has the appliance has entered the information.
The appliance would have a packet radio, a PC104 computer,
and a hard drive. You'd tell it what areas and readings
you were interested in, and how much hard drive space
you're willing to devote to data meeting various criteria,
and the application would take care of maintaining the
database, deciding which data to keep and which to delete
with new updates, sharing information with other boats,
and possibly even some minor network services like a
store-and-forward service for messages.
Bear
On Wed, 10 Nov 2004 01:46:34 GMT, <····@sonic.net> wrote:
> Karl A. Krueger wrote:
>> One of our researchers here at WHOI is building a new system to allow
>> multiple vessels to dial up a shore station (using Iridium modems) to
>> deliver data files. The shore station is planned to have a single
>> modem. I was curious just how many callers we can expect to service on
>> a single modem without formal scheduling, given that they make calls
>> with varying frequency and for varying durations.
>>
>> I haven't been given any actual figures for frequency and duration, so I
>> can't actually do the math for it yet. But it seemed like a moderately
>> interesting problem, so I tossed together a really cheap & primitive
>> simulation using CLOS objects to represent callers with different
>> requirements.
>>
>
> This is interesting....
>
> I've been considering a packet-radio peer-to-peer
> local-information sharing application for boaters as
> a possible thing to develop.
>
> All of these guys have electronic charts and GPS. But
> often the charts are outdated or wrong, so they also
> have to have instruments: Everything from depthsounders
> to weather indicators. And despite advances, internet
> connectivity on the water tends to be low-bandwidth,
> expensive, spotty, and unreliable, especially far from
> shore or in pristine parts of the world that are far
> from overdevelopment. Boat-to-boat contacts can be
> had in many situations where shore stations can't reach
> or in areas of the world where shore stations are not
> installed, and radio waves are more-or-less free.
There is a package of software in the ham community that should be
adaptable for your needs. The weblink I had is dead, but the package
is a spinoff of the DXCluster software, it had provisions for lat,
long and weather information as I recall. Ham packet is setup for
much of the conditions you mention, so they are probably a good
resource (in many ways).
--
Brownian motion is correctly colored.