Lecture Notes for Simulation

6 April 2005 - An Ethernet Simulation

Outline

• Ethernet-style protocols.

• Ethernet

• The simulation objectives.

  • Inputs, outputs, and characterisitcs.

• System analysis and assumptions.

  • Host and network behavior.

• Modeling

  • Implementation techniques.

  • Network and host behavior.

Random Multiple Access

• A set of hosts connected by a shared, effectively broadcast medium.

• A random multiple access protocol has each host scheduling its media access.

  • Media access is globally random, with no overall coordination.

• The ALOHA protocol was the first random media access protocol.

  1. Each host transmits packets as they become available.

  2. If an acknowledgement arrives within two round-trip times, the transmission is complete.

  3. If the ack times out, the host delays for a random time and goes back to step one.

• The round-trip time and random back-off are key points.

Carrier-Sense Multiple Access

• Packet collisions cost two round-trip times in random multiple access protocols.

• A carrier-sense multiple access (CSMA) protocol reduces collisions by having a host listen before transmitting a packet.

  1. When a packet becomes available, sense the medium.

     • If the medium is busy, delay a random time and go to step 1.

     • If the medium is idle, transmit the packet.

  2. If an acknowledgement arrives within two round-trip times, the transmission is complete.

  3. If the ack times out, the host delays for a random time and goes back to step one.

CSMA with Collision Detection

• CSMA protocols can still collide during near-simultanious transmission.

• Carrier sense media access with collision detection (CSMA/CD) protocols have the host listen during transmission too.

  • If the packet heard doesn't match the packet sent, a collision occured during transmission.

  • Transmission can be aborted immediately, followed by back-off.

• The IEEE 802.3 standards describe the Ethernet CSMA/CD protocols.

Ethernet

• We'll be dealing with 10 Mbit/sec (10 BaseT) Ethernet.

• Media access is specified in terms of slot size.

  • Maximum cable length is 500 m.

  • There may be up to five cables in a segment (repeaters ignored).

  • Propigation delay is 0.6 the speed of light (0.2 km/us).

  • The packet size is 64 bytes.

  • The slot size (transmission time) is
    (64 by/pkt)(8 bi/by)/(10 mbi/s) = 51.2 us/pkt.

Ethernet Back-Off

• When collisions occur, the host backs off for a random time before retransmitting.

• Ethernet uses binary exponential back-off at each host.

• A host delays d slot times on each collision.

  • d drawn from a uniform distribution with range 0 to 2^{max(i, 10)} - 1.

  • i is the number of collisions encountered by the current packet.

    • i = 0 for each new packet sent.

  • Transmission is aborted when i > 16.

Simulation Objectives

• Determine protocol efficiency when

  1. the packet size is either 256 or 1024 bytes,

  2. the average number of waiting transmitters varies between 0 and 8 (inclusive), and

  3. all hosts always have a packet to transmit.

  • Protcol efficienty is (capacity used)/(capacity available).

• Determine how transmission delay varies with protocol efficiency for packet sizes of 256 and 1024 bytes.

• Results should be given with 95% confidence.

System Assumptions

• The hardware works without problem.

  • Hosts are reliable.

  • The cable is noiseless and perfectly absorbing.

  • Hosts are uniformly distributed along the cable (uniform delay).

  • The effective cable length provides the maximum allowed delay.

    • This assumption gets rid of repeaters but results in a cable that's too long.

    • The effective length is (51.2 us)(200 m/us) = 10 km.

• The mean delay between successive transmission at a host is eponentially distributed.

  • For protocol efficiency, the mean is 0.

Simulation Inputs

• The frame size, either 256 or 1024 bytes.

• The number of hosts.

• The mean delay between transmissions (successful or not) at each host.

Simulation Outputs

• The average number of hosts waiting to transmit.

  • Used in the efficiency vs. hosts plot.

• The total transmission delay, measured from the start of the first transmission to the start of the first successful transmission.

  • A packet transmitted successfully on the first try has 0 transmission delay.

  • Used in the delay vs. efficiency plot.

• The total number of successfully transmitted packets.

  • Used to compute protocol efficiency.

  • Efficiency = N_sent/N_possible.

    • N_possible = (10 mbi/s)(t s)/((8 bi/by)(p by/pkt))

    • t is the simulation duration; p is the packet size.

Simulation Characterisitcs

• Confidence intervals require several sets of simulation results.

• The requested results are not comparitive, so runs may be independent.

• Using block means is eaiser, if less accurate, than using run repetition.

• Simulation parameters include

  • Transient length.

  • Simulation duration.

  • Block count.

  • Random number seed.

  • Jam signal duration.

System Analysys

• The hosts, the network, and the packets are possible simulation entities.

• Given its complexity, a host is an entity.

• The network can be used to schedule packet deleveries.

  • Packet delivery is (almost) deterministic, but requires the network topology.

  • Moving the network topology to the network entity simplifies hosts.

• The packets seem simple enough to fold them into events.

Host Behavior

• Contention - delay for the random exponential back-off; the send fails after 16 attempts.

• Listen - for 2 r.t.t to detect other packets being sent.

• Send - for large packets, the transmission time in excess of 2 r.t.t.

Network Propagation

Some observations: Propagation is deterministic. But it depends on host topology. Network status is location dependent. Some conclusions: The network should schedule packet arrivals and departures at hosts. Each host should keep track of network status.

Network Behavior

• Packet sends are indicated by separate packet-start and packet-end events.

  • This simplifies collision behavior.

• Propagating is a pseudo-state representing packet-event scheduling.

  • The network's always in the waiting state.

Simulation Events

• Packet transmission:

  • packet-detection starts.

  • packet-detection ends.

• Delay expiry:

  • Two round-trip-time delay

  • Back-off delay.

  • Packet inter-arrival time.

Implementation Techniques

• Implementation is based on finte-state machines (FSM).

  • Entities are subclasses of the FSM class.

  • Events are inputs to the FSMs.

• The Smalltalk simulation represents transition actions as blocks.

  • A block is an anonymous, lexically scoped function.

• The C++ simulation implements the FSM with the visitor pattern.

The Network Entity

• The only relevent events for the network are packet-detection starts and ends.

  
  inState: waiting forEvent: packetStarts do: 
    [ self schedule: packetStarts ]
  
  
  inState: waiting forEvent: packetEnds do: 
    [ self schedule: packetEnds ]
  
  
  schedule: packetEvent
  
    'Schedule event arrival at every host 
     but the event sender.'
  
    waiting
  

Host Send Request

inState: idle forEvent: newPacket do: [ 
  assert waitingPackets = 0
  self enqueuePacket
  waiting ]


enqueuePacket
  waitingPackets++
  eventQueue 
    delay: newPacket 
    utill: packetArrivals next
    for: self


inState: default forEvent: newPacket do: [ 
  assert queuedPackets > 0
  self repacket
  self currentState ]

Host Back-Off Expires

inState contention forEvent BackoffDone do:
  [ retries++ > 16
      ifTrue: [ self dequeuPacket ]
      ifFalse: [ self transmit ] ]


dequeuePacket
  assert queuedPackets > 0
  --queuedPackets > 0
    ifTrue: [ self transmit ]
    ifFalse: [ idle ]


transmit
  networkIdle
    ifTrue: [ sendAndListen ]
    ifFalse: [ waiting ]

Data Collection

• The simulation should plot host delays and send delays against protocol efficiency.

  • Protocol efficiency is actual over possible packets sent.

• Two sample streams will do: host delays and send delays.

  • Everything else can be derived from the sample streams (packets sent from the send delays) or computed (the possible packets sent).

• Data are written to separate text files, one sample per line.

Detecting Steady State

• Moving-average analysis over the host-waiting samples produces straightforward results.

• Host delay quickly (within 25 samples) reaches steady state.

Delay Steady State

• Moving-average analysis over the packet-delay samples is less straightforward.

• This is an example of self-similar behavior.

  • Dealing with self-similar behavior is complicated.

  • Throw away the first 80% of the samples.

Experiment Set-Up

• Both graphs are measured against

  • 256- and 1024-byte packet sizes and

  • 0 to 8 waiting-hosts averages.

• Packet size is a simulation parameter.

• Waiting-host transient analysis sugggests that, out of n hosts, n - 1.5 are waiting at any time.

  • This is when the inter-packet arrival gap is 1.0 usec.

  • When the gap is 0, it seems reasonable that n - 1 hosts are waiting.

  • Host count n is a simulation parameter.

• Data collection will require 2x9 = 18 runs.

Block Means Design

• Given the accuracy requirements, data can be collected using block means.

• Using the magic 30, assume there'll be at least 30 blocks, say 40.

• The samples per block is usually related to the transient size.

  • The transient size is either small (< 25 for waiters) or huge (80% for delay).

  • Use the magic 30 samples with 10 extra for safety.

• The simulation should produce around (40*40)/(1 - 0.8) = 8000 samples.

  • At 25 msec per sample, the simulation should take around 8000*25 = 200,000 msec = 3 minutes per run.

  • Total simulation time should be around 18*3 = 54 minutes.

The 256-Byte Packet Results

	Protocol efficiency			Transmission delay			Waiting hosts
	Mean	Std.	95%	Mean	Std.	95%	Mean	Std.	95%
Run	%	dev.	conf	usec	dev.	conf	hosts	dev.	conf
3	63.1	8.5	3.1	150.73	485.56	13.75	1.85	0.71	0.03
4	62.9	9.4	3.4	230.13	583.96	17.05	2.79	0.72	0.02
5	61.5	7.3	2.6	315.20	670.23	20.04	3.76	0.72	0.02
6	60.9	9.0	3.2	375.58	769.90	23.47	4.73	0.72	0.02
7	60.1	5.1	1.8	504.25	1077.01	33.91	5.71	0.74	0.02
8	60.1	12.6	4.5	530.41	1026.98	32.41	6.69	0.73	0.02
9	60.2	3.2	1.2	625.90	1177.53	38.21	7.69	0.74	0.02

The 1024-Byte Packet Results

	Protocol efficiency			Transmission delay			Waiting hosts
	Mean	Std.	95%	Mean	Std.	95%	Mean	Std.	95%
Run	%	dev.	conf	usec	dev.	conf	hosts	dev.	conf
3	93.1	3.83	1.3	147.35	585.03	16.43	1.85	0.71	0.03
4	92.9	1.2	2.2	233.01	587.74	17.24	2.79	0.72	0.02
5	91.4	2.0	7.4	318.41	729.72	21.91	3.75	0.73	0.02
6	90.6	2.9	8.0	398.02	836.67	25.66	4.74	0.72	0.02
7	90.5	3.6	7.4	514.14	1247.90	39.29	5.72	0.73	0.02
8	90.2	1.4	2.3	615.52	1121.50	36.26	6.69	0.74	0.02
9	90.3	2.3	3.3	645.61	1421.98	46.38	7.68	0.74	0.02

Final Results

Points to Remember

This page last modified on 19 April 2005.