New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Computer Networks

by: Ashleigh Dare

Computer Networks ECS 152A

Ashleigh Dare
GPA 3.75


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in Engineering Computer Science

This 10 page Class Notes was uploaded by Ashleigh Dare on Tuesday September 8, 2015. The Class Notes belongs to ECS 152A at University of California - Davis taught by Staff in Fall. Since its upload, it has received 59 views. For similar materials see /class/191707/ecs-152a-university-of-california-davis in Engineering Computer Science at University of California - Davis.

Similar to ECS 152A at UCD

Popular in Engineering Computer Science


Reviews for Computer Networks


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/08/15
Tien Tieu ECS 152A Phase II Program INSTRUCTIONS To compile type make all This will make the executables for all 4 versions of my program a b c and d Program README My program consists of 4 classes and several static functions along with some global static Variables Below is a breakup and explanation of each if something is not listed it is either unimportant or no longer used in phase 2 or is selfeexplanatory Static global variables static const double mul l This array contains the Values of mu This is not of Very much important in phase 2 since we don t really use it anymore 001 002 003 EAL f T I Lt 20 L K using Again mu is not really static int samples 100000 This is the number of packets that need to be transmitted before the simulation finishes static double globalitime This Variable holds the current time L A used in Static functions static double negiexpidistritimedouble rate 7quot 3U rjr rv39virv m L t git static int min int a int 19 This function returns the minimum of two input integers static int myRandint max This function generates a random integer of range 0 lt r lt max static int myEXpint k This function computes powers of 2 ie returns 2Ak where k is the in put integer static int backoffiamoun int n This function computes the amount of backoff Classes Class Packet This is the packet class doublyelinked list elements duration time needed to transmit the packet r edone number of as undergone pid packet id used for debugging and Members include and of course the list pointers transmission attempts this packet seeing how the packets move through the simulation Member functions include constructor initializes class members accordingly display displays info about the packet Class Event This is the event class also doublyelinked list elements Members include type either arrival or departure time time packet arrives or time it is ready for departure eid event id sed for debugging and seeing how the packets move through the simulation pack the packet that the event carries and of course the list poin ers Member functions include constructor initializes class members accordingly display displays info about the even Class GEL This is the global event list doublyelinked event list the first event in the GEL end the last event in the GEL nto the GEL ordered by time remove nt id s of events Members include front Member functions include insert inserts an event 1 irst event from the list dis lay neatly outputs the d M savior when debugging and making sure the program worked the way it was supposed tol Class buffer This is the buffer class which acts as a queue doublyelinked packet list Memb ers include front the first packet in the queue end the last packet in the queue how it was supposed tol packets ready for transmission when a collision occurs eeps track of how many times the packet has attempted retransmission There are four versions of the program a k minn10 exponential Olt1 lt2k b k minn10 linear 0ltrlt2k c k minn3 exponential Olt1 lt2k d k minn3 linear 0ltrlt Each program runs automatically for all values of A 001 002 003 004 005 006 008 The way my program works is as following 1 There are 10 arrival GEL s one for each host that generate events at the same rate A 2 When event time gt global time the event is ready to use ie this simulates the event arriving at this time so we get an arrival rate of A Once ready it is pulled from its GEL and put into its departure GEL also 10 one for each host 3 When the host is ready ie departure event time gt global time the host will fetch the packet from the departure event and put it on the queue also 10 one for each host 4 If there are more than one host ready to transmit we get a collision and the backoff algorithm is called Otherwise we transmit the packet and advance the time accordingly 5 Simulation ends when 100000 packets have been sent A key note is that the program advances the time in ticks except when a transmission is in progress The tick value given by our program specs is Ts 1 so that is what is used Also due to the sheer number of collisions parts B C and D have very low utilization rates This is a result of having too small a range used for our random backoff function Part A didn t suffer too much of a problem from collisions since it s max backoff range was 2 10 which is 1024 much higher than that of 20 for version A 6 for version C and 8 for version D Also a change I made to the backoff algorithm is as follows when a collision occurs the packet that has the highest number of retransmission attempts gets highest priority That is it gets transmitted first while the others get pushed back I made this slight change in response to a seemingly almost infinite loop that occurred when there were too many packets waiting to be transmitted Even after the backoff algorithm was run there would still be too many packets still waiting so we run into an infinite loop of applying the backoff algorithm and still getting collisions A simple example of this is to look at an extreme case when each of the 10 hosts has X packets on the queue waiting to be transmitted where X the max backoff amount If we run the backoff algorithm the most that a packet can be pushed back is X ticks but since there are X packets each and every host will still have one packet ready to transmit at the end of the next Tien Tieu ECS 152A Phase II Network LAN SiEElation Aqglysisphase II There are four versions of the program a k minn10 exponential 0 lt r lt 2k b k 39nnlO linear 0 lt r lt 2k c k minn3 exponential 0 lt r lt 2k d k 39nn3 linear 0 lt r lt 2 Since there are N 10 hosts and our A values are 001 002 003 004 005 006 008 Ideally we should expect to get a utilization of somewhere around U 01 02 03 04 05 06 08 This is due to the total arrival rate Total arrival rate 10 A However this result is only possible if we had not have had any collisions or we possessed a much better way of dealing with them But with the backoff algorithms we were given to deal with collisions ere we pushed back all transmission instead of pushing them on a queue and transmitting in order we would expect a moderately lower utilization rate than that above This is because of the nature of our backoff algorithm Sometimes we push back all processes a range of 0 lt r lt 2minn10 but since the values are randomly chosen sometimes we get wasted time That is it is not often that we have a process pushed back only by a value of 0 and if none of the ready packets get pushed back by 0 we waste time equal to the minimum of all the backoff given to each of the colliding processes since it would take this long minimum before any packet will be ready to transmit again Eg if two hosts try to transmit we get a collision and have to push back both requests Say for the sake of argument that one of these requests gets a backoff value of 10 the maximum allowed which is very possible at times If the first request got a backoff value of 7 it won t begin transmitting until 7 ticks afterwards and hence we have 7 wasted ticks Also should the first request finishes before the second can start again and if there are no other requests pending we again get wasted time And should both requests receive the same backoff amount we get the most wasted time yet In this case when they are both ready they will have another collision and again so as long as they receive the same backoff amount Our examples above represent a case where 2 packets collide But the truth of the matter is we are more likely to waste even more time when more than 2 packets collide My results provide an example of the instances provided above in which time is wasted The order of efficiency of the programs is version A version B version C and version D ordered from most to least efficient respectively This can be explained as so Max backoff ranges Version A lt r lt 2 10 0 lt r lt 1024 Version B 0 lt r lt 210 399 0 lt r lt 20 Version C 0 lt r lt 2 3 9 0 lt r lt 8 Version D 0 lt r lt 23 9 0 lt r lt 6 From the examples of cases in which we can waste time with the backoff algorithm given previously we can see why this is the case version A the backoff range is 1024 so the colliding processes are less likely to repeatedly receive the same backoff and repeatedly waste time As the range decreases the chances that one backoff amount given to a colliding process will match that given to another colliding process increases For version D this is the worst In the worst case scenario we will have 10 colliding processes and a range of only so many values possible for the backoff hence for versions C and D we are guaranteed that at least a few of the packets will be back in another collision and hence waste time If they happen to have received the smallest backoff amount given they will tie down the system in needless wasted time Although this accounts for the most wasted time we cannot just go out and drastically increase the range for the backoff algorithm This is because higher ranges for our backoff algorithm also waste time eg if our range was 0 lt r lt 50000 it would be very slow since it we will be pushing back packets by a drastic amount of time wasting time in between An example is if we had that range and two colliding processes and both receive very large backoff amounts say 40000 and 45000 it s random so is quite possible the transmitter will have nothing to do for the first 40000 ticks after applying the backoff algorithm wasting a huge amount of time Hence the moral is to select a backoff range that is large enough so that we don t receive repeated collisions and at the same time select one that is small enough so that we don t waste so much time Pondering it over I think a lot of the discrepancies in the results are caused by our ramdom number generators They are in fact not so random at all Two ways which I thought of implementing a way to fix the backoff algorithm is l to give priority to the packet which has undergone the highest number of attempts at retransmission out of all the colliding processes I would transmit this packet right away and then apply the backoff algorithm 2 As for the backoff algorithm I would make sure that no two colliding processes will receive the same backoff amount since this will cause another collision if they do receive the same amount All in all I think that a simple queue would be one of the best ways to implement the selection of which packet to send first Just transmit whichever packet arrives first and if more than one arrives concurrently give the smallest packets priority over the larger packets Simulation Results Version A K min n10 0 lt rlt 2quotk exponential 002 003 004 005 Utilization 0057058 0108495 0158473 0201772 023635 0274295 0310053 Version B K min n10 0 lt rlt 2k linear Rate A 001 002 003 004 005 006 008 Utilization 0015589 0031704 005721 0068507 0103316 0106765 0162275 Version C K minn3 0 lt rlt 2quotk exponential Rate A 001 002 003 004 005 006 008 Utilization 0014455 002767 0044513 0058439 0055882 006205 0069026 Version D K minn3 0 lt rlt 2k linear Rate A 001 002 003 004 005 006 008 Utilization 0011525 0015564 001623 0033547 0040676 0047066 0051907 uongngn BBBJBAV 025 015 Utilization vs Rate Version A K minn10 exponential backoff 001 002 003 004 005 Rate 006 007 008 009 uongngn BBBJBAV 012 008 006 004 Utilization vs Rate Version B K minn10 linear backoff 001 002 003 004 Rate 005 006 007 008 uongngn BBBJBAV 006 005 004 003 002 Utilization vs Rate Version C O K minn3 exponential backoff 001 002 003 004 Rate 005 006 007 008 009 uongngn BBBJBAV 004 003 002 Utilization vs Rate Version D K minn3 linear backoff 001 002 003 004 005 Rate 006 007 008


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Anthony Lee UC Santa Barbara

"I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.