Unix Programming

Author

CSMA

rishi.shah@patni.com

2005-09-24, 6:58 pm

I am implementing a project in c++/unix in which I need to simulate a
CSMA MAC layer.
The project is a simulation of peer to peer network where is each peer
is a process on some unix machine. Though each client has a separate
TCP communication line, I have to assume that they have a common line
and each of the process has to follow the CSMA mechanism while
transmitting that is if there is a collision while transmitting then
both the processes have to revert back and transmit after some random
interval of time. I have to assume that the entire network is runnning
on a 9.6kbps line. Each peer notifies every other client if it sends a
packet on the common line.
I am struggling as to how to design such a network where I have to
detect a collision since there is no delay in the unix socket
communication. One idea could be to send the packet to a recipient,
wait for x msec and then send a signal to the recipeint to go ahead. If
the sender receives a packet from some other source during the xmsec
wait time then it will not send the signal and the recipient will
discard the packet.
Are there any better ideas to solve this problem?

Pascal Bourguignon

2005-09-24, 6:58 pm

"rishi.shah@patni.com" <rishi.shah@patni.com> writes:

> I am implementing a project in c++/unix in which I need to simulate a
> CSMA MAC layer.
> The project is a simulation of peer to peer network where is each peer
> is a process on some unix machine. Though each client has a separate
> TCP communication line, I have to assume that they have a common line
> and each of the process has to follow the CSMA mechanism while
> transmitting that is if there is a collision while transmitting then
> both the processes have to revert back and transmit after some random
> interval of time. I have to assume that the entire network is runnning
> on a 9.6kbps line. Each peer notifies every other client if it sends a
> packet on the common line.
> I am struggling as to how to design such a network where I have to
> detect a collision since there is no delay in the unix socket
> communication. One idea could be to send the packet to a recipient,
> wait for x msec and then send a signal to the recipeint to go ahead. If
> the sender receives a packet from some other source during the xmsec
> wait time then it will not send the signal and the recipient will
> discard the packet.
> Are there any better ideas to solve this problem?

You need to have a line object and some packet objects, and the line
objects will be given packet objects at times and will compute when
there's a colision.

If your simulation runs on a distributed network, you have to maintain
a common clock to avoid some remote node sending packets in the past.

--
"I have challenged the entire quality assurance team to a Bat-Leth
contest. They will not concern us again."

rishi.shah@patni.com

2005-09-24, 6:58 pm

I could not follow what exactly you meant by line objects and packet
objects.
Please expand upon that.

SM Ryan

2005-09-24, 6:58 pm

"rishi.shah@patni.com" <rishi.shah@patni.com> wrote:

# I am struggling as to how to design such a network where I have to
# detect a collision since there is no delay in the unix socket
# communication. One idea could be to send the packet to a recipient,

If I understand your question, in various aloha networks the sender
is not usually responsible for detecting collisions. The speed of
light is not instanteous, so its possble the sender doesn't even
know there was a collision. In case of a collision, the packet
will be corrupted and with a very high probability the frame or
CRC checks will fail, so that no receiver accepts the packet. If
the packet is not acknowledged with an acceptable time, it is
retransmitted after a random delay.

Carrier sense is akin to clearing your throat to announce you
will be talking. Hopefully other senders will hear that before
they clear their throats as well.

--
SM Ryan http://www.rawbw.com/~wyrmwif/
GERBILS
GERBILS
GERBILS

Pascal Bourguignon

2005-09-24, 6:58 pm

"rishi.shah@patni.com" <rishi.shah@patni.com> writes:
> I could not follow what exactly you meant by line objects and packet
> objects.
> Please expand upon that.

Yes. In a simulation, you'll have to program explicitely models of the
objects and phenomenons you're simulating. If you just implement a
network over an actual network, you hardly have a simulation. As
you've noticed, you can get collisions with TCP because TCP is two
layers above where colisions are resolved.

Object Oriented programming is a perfect match for simulations. It's
in this domain that OO has been invented with Simula, the first OO
language.

The fact that you make a distributed implementation of your simulator
is rather irrelevant: you could have all the objects of your
simulation inside one process. There's no strong point to put some
objects on some other computer and have them communicate via TCP. This
can help having a speedier simulation if the objects were heavily
CPU-bound, but this is not the case, you're trying to simulate I/O...

So, an ethernet cable (line) object will receive packets at different
times at different points of the cable. From the length (duration of
transmission) of the packet and the position of the various receivers,
you can compute whether each receivers get a colision or not. Note
that you can send two packets from each ends of an ethernet cable and
not get a colision at the other ends: the packets "cross" each other
in the middle and only a receiver in the middle could see a colision,
but if the other packet is received after the sent one, then no
collision occurs.

t:0 if-1 and if-3 start sending each a packet of duration d
if-1 if-2 if-3
+---------------------------+----------------------------+

t:d/2
if-1 if-2 if-3
+////-----------------------+------------------------\\\\+

t:d the packets are sent
if-1 if-2 if-3
+////////-------------------+--------------------\\\\\\\\+

t:d+x colision starts at if-2; if-2 will need a resent
if-1 if-2 if-3
+--------------------///////X\\\\\\\---------------------+

t:d+x+d/2 full colision at if-2
if-1 if-2 if-3
+-----------------------XXXXXXXX-------------------------+

t:d+y colision ends at if-2
if-1 if-2 if-3
+-------------------\\\\\\\\+////////--------------------+

t:d+z if-1 and if-3 start receiving the other's packet without colision
if-1 if-2 if-3
+\\\\\\\\-------------------+--------------------////////+

t:d+z+d if-1 and if-3 have received each the other's packet successfully
if-1 if-2 if-3
+---------------------------+----------------------------+

Note that a packet sent from if-2 will propagate duplicated:

if-1 if-2 if-3
+---------------------------+----------------------------+

if-1 if-2 if-3
+--------------------------/+/---------------------------+

if-1 if-2 if-3
+-------------------------//+//--------------------------+

if-1 if-2 if-3
+------------------------///+///-------------------------+

if-1 if-2 if-3
+-----------------------///-+-///------------------------+

if-1 if-2 if-3
+----------------------///--+--///-----------------------+

and of course, you could have a colision if-2xif-3 while at the same
time if-1 would receive the packet from if-2 correctly.

So you have the objects:

Cable
length-in-meter
propagation-speed (m/s)

Interface
attached-to-cable
position
speed-of-transmission (b/s)

Packet
length-in-bit

So the Interface objects will receive Packets from packet generators,
will simluate some protocol stack queuing, and will decide at what
time to send the next packet, telling the Cable object: I start
transmiting a packet. The Cable object will have to track the
transmission in progress, and compute the position of each packets,
and signal the interface whether they're earing a clear bit from a
packet or whether they're earing a colision or silence at any given
time.

Since the Cable object will advance the clock to make the packet move,
if you implement the Interface objects on distributed hosts, you'll
have to inform them of the time to avoid them sending packets in the
past. You need to explicitely state the times, since using TCP you
can receive messages from different hosts out of order, real-clock wise.
Do you really have to make a distributed simulation?

--
__Pascal Bourguignon__ http://www.informatimago.com/
Kitty like plastic.
Confuses for litter box.
Don't leave tarp around.

Alex Fraser

2005-09-25, 7:57 am

<rishi.shah@patni.com> wrote in message
news:1127596352.312029.273640@z14g2000cwz.googlegroups.com...
> I am implementing a project in c++/unix in which I need to simulate a
> CSMA MAC layer.
> The project is a simulation of peer to peer network where is each peer
> is a process on some unix machine. Though each client has a separate
> TCP communication line, I have to assume that they have a common line
> and each of the process has to follow the CSMA mechanism while
> transmitting that is if there is a collision while transmitting then
> both the processes have to revert back and transmit after some random
> interval of time. I have to assume that the entire network is runnning
> on a 9.6kbps line. Each peer notifies every other client if it sends a
> packet on the common line.
> I am struggling as to how to design such a network where I have to
> detect a collision since there is no delay in the unix socket
> communication. One idea could be to send the packet to a recipient,
> wait for x msec and then send a signal to the recipeint to go ahead. If
> the sender receives a packet from some other source during the xmsec
> wait time then it will not send the signal and the recipient will
> discard the packet.

I presume you intend to handle the case where A sends to B at the same time
as C sends to D.

Note that AIUI, in a half-duplex Ethernet network compliant with the
specification, a collision anywhere will always be detected by the senders.
Thus the situation Pascal described where the packets cross on the
transmission line does not occur. The guarantee is provided by specifying
that the minimum transmission time (implied by way of a minimum frame size)
is longer than the maximum propagation time between any two nodes. I think
simulating this simplifies matters.

Another thing that would almost certainly simplify the problem (timing
issues in particular) is having all transmissions go via a "hub" process, if
that is an option.

You might be better off asking about this in another group such as
comp.programming since the difficulties are not Unix-specific.

Alex

Sponsored Links