RSS

Trafficking…

19 Dec

I am someone who likes to understand concepts through analogies. If I can’t get to analyse a problem using an analogy that everyone can relate to, I will try to refrain working on it. The corollary is that, if someone cannot given me an analogy for a problem or solution, I will be more inclined to think that they dont have a clear understanding of the problem at hand…Anyway, being in the networking world and talking all about traffic engineering for a living, it is very logical for me to analyse these problems using the real life traffic. I found some of the results amusing…:)

While we have figured out how to get the internet traffic to get faster and more reliably decades ago, we are still getting stuck in our regular traffic to work. As you all know, a given networking link is characterized by how much traffic it can carry (bandwidth) and how much time it takes to carry (latency). Reliability is a relative word and I dont think it has much relevance to my following analysis. The question now is, what is the bandwidth of a freeway? Well, we measure network traffic is bits per second. For freeway, let us assume that it is cars per second. We could later change that definition to be passengers per second. For now, assume that there is 1 passenger per car.

Let us do some math. At 65 miles per hour speed, and an average car length of 5 meters, the number of cars per second is about 5.72, we can approximate it to 5 (since the trucks and the minimum gap between cars should be discounted for fairness). If we have 4 lanes, this comes to 20 cars per second or 1200 cars per minute. The two sided nature of the problem is that, the traffic is really heavy only 2 times in a day for around 6 hours. Provisioning the road to account for the peak case is the obvious solution, but a bad one too. In the networking world, we call it bursty traffic. Let us say, we want to double the traffic in a given freeway, what are our options? The obvious ones are (i) Make the cars twice as fast (ii) Make the road twice as wide, change it from 4 to 8 lanes (iii) Accomodate 2 passengers on each car (iv) Make the car half the length. Knowing what we know, (i) & (iv) are not easy to do, (iii) is the equivalent of enforced car pooling and (ii) has a cost associated. We could have different priorities with high priority cars or vehicles being the ones carrying more passengers versus ones with smaller number of passengers which in turn can transport more passengers per second since the larger passengers are grouped into a single lane. We could have alternative modes like trains and hope that passengers would take trains instead of cars, in which case the problem centers around how many passengers we can transport per second.

Ideally, if we make a big enough vehicle that can accomodate all the passengers to a given destination city, that is the best we can do. I just checked up that BART service here in bay area can carry a comfortable load of 700 people in a 750 feet train (225 metres) at an average speed of 36 mph (considering stops at stations). Now, if we had enough trains to carry people around, the ratio between car-passengers/second and train-passengers/second is 20 versus 50 passengers. Only a 2.5 speedup and the extra wait time in station to get into the train and back. Again, we can try to optimize by double-decking the train since adding additional railway line can be quite expensive, assuming the rails can handle it. Also, having non-stop service can increase the speed by 2 or 3 fold which can give benefits too. Remember that, the more the wait time to get to a train, the latency increases. In some cases, the bandwidth can look great if we wait long enough to accomodate as many passengers as we can. But, the time to get to a destination will suffer terribly.

Now, if you would substitute cars with packets, passengers with cells (fixed size units which makes up a packet), transmission rate or capacity to bandwidth, the same kind of problems exist in networking and the same kind of problems are applicable there too. The parts that are easy in networking are that, creating wider lanes with high capacity is becoming increasingly easy and cost effective. The part that has always been difficult is to handle burstiness of traffic. Though there are many solutions, optimality is questionable. Another thing that is possible in networking is the use of a scheduler. If we exactly knew which routes were free and how many people want to get to a given destination ahead of time, we can allocate their paths for optimality. But then, when everybody is bursting in all at the same time, scheduler optimality is not guaranteed and that is still a problem. Well, that’s all folks. You have survived yet another round of my random rambling session…Congratulations!

Advertisements
 
12 Comments

Posted by on December 19, 2007 in From AM-KICKING blog, Informative

 

12 responses to “Trafficking…

  1. Manohar

    December 20, 2007 at 6:15 am

    Lovely writeup and an excellent analogy. But somehow I thought long and hard about the first sentence.. and atleast in mycase.. I realised that many times looking for an analogy has diluted my undertanding or prevented me from truly understanding the original issue. The reason, atleast for me is that.. an analogy is only good so far… its just an analogy not really the orginal problem. In looking for an analogy sometimes we have to make approximations. Again this is not always but a lot of times.

     
  2. Mindframes

    December 20, 2007 at 6:25 pm

    U r right about the analogy case. Sometimes, I do get frustrated when things get condensed to a form which sways too much from the original…I like to think of analogies as more for beginners…more like an eye opener…something that creates a framework to induce thinking and creativity… In a lot of cases, I’ve experienced that such big-picture view helps a lot…

     
  3. Mad Max

    December 20, 2007 at 11:23 pm

    Very nice write up mindframes. I guess I will buy your arguments but is the analogy the best we can come up with?

    Here is my point. Let us break the problem of networking into a single issue. Transferring data from node 1 to node 10. From my very very very limited knowledge of these things, my understanding is that we can use something like a constrained shortest path algorithm (where the choice of routes could probably be millions) where constraints can be placed on peak loads, time to delivery etc etc. The very fact that each of these factors can be controlled (I’m assuming assume that there are optimized algorithms to reduce the signal to noise ratio). If the noise level is higher, then there is loss of efficiency. Further would it be fair to say that the number of algorithms that exist are finite and can be controlled to a large extent?

    Now the analogy with transport can be a little disconcerting. This is probably again because people always dont use a strict decision rule. If I were to ask the question : Do you always take Route 77 to go to work? some might say yes and some might say no and further some might say maybe. The question now comes to reasons. There can be several reasons why a particular path need not be chosen. Are such reasons finite in this case? Further I might choose to take Route 77 today because it is the optimal route but tomorrow I might choose Route 88 which is the least optimal. Why so? Again the reasons can be bizzare.

    Again going to your example on how to accomodate twice that many cars. Each solution is costly. The question is how much cost does each person place on the suggested alternative. In the case of the networking world, that cost is likely to be exogenous (in the sense that absolute resource costs are exogenous). In the case of transport choice there are too many endogenous personal variables which vary from one individual to the other.

    Hence the critical difference between the two examples is the level of heterogeneity in responses. This can have significant (even reverse) impact on inferences drawn.

    If we believe this, then would this still be a good analogy? Or would it be hard to believe that such heterogeneity among individuals exist? Or would it be wrong to say that networking has relatively lower levels of heterogeneity in implementation?

    Questions to ponder??? maybe not! πŸ™‚

     
  4. Mindframes

    December 21, 2007 at 1:29 am

    I can now figure what mano was trying to say…Trying to find an analogy to answer your question seems incomprehensible..:)

    I agree with you on that, if you make the problem revolve around individuals and why they make the choices they do and the cost they place, the inferences drawn could be different. But, I wasnt trying to solve the problem by considering the individual’s preference as a constraint. But rather, the society as a whole which in turn could present attractive choices for an individual.

    As a matter of fact, if you take a problem and assume that stupidity as a more prominent case, then a lot of the solutions wouldn’t converge and that could be why such problems are not yet solved in the first place…:)…It is possible that one can only apply some heuristics and hope for the situation to get better… But remember, I was trying to draw an analogy…

    I dont see why road-traffic is any different (if you take out individual decision making skills)… The problem remains that, person A wants to get from position X to position Y in the shortest time possible. There are infinite ways to get there, but the efficient ways and modes to get there are finite. In this case, arrival pattern is random, but peaks during a given time window. Constraints that mainly govern this are limited to road-speed, number of lanes and the number of passengers per car/object which, in my opinion is the same in the networking world unless I am missing something…

     
  5. Mad Max

    December 21, 2007 at 8:13 am

    @ Mindframes: To the last paragraph..”…The problem remains that, person A wants to get from position X to position Y in the shortest time possible…”. I’m not sure if this is always the case. That was my point. If it was then point taken and I think the analogy is fairly easy to comprehend.

    But people by not choosing the shortest path are not necessarily irrational. They could have other reasons such as “just feel like driving on this particular route” for instance. Though it might not be the shortest, it achieves the objective of getting person A from point X to Y and also keeps A happy.

    That was my argument. By putting in the constraint “shortest path”, the two problems are similar. But is “shortest path” the most efficient? The answer will vary with individuals. I guess that is what I was really trying to drive at.

     
  6. Mindframes

    December 21, 2007 at 4:46 pm

    Gotcha… Now, we will have to get into the probability of a given person to take a longer/comfortable route versus taking a shorter route versus taking a faster route, in the “peak” hours… Remember, the worst case to this problem is the peak traffic conditions…

     
  7. Saumya

    December 21, 2007 at 7:10 pm

    Nicely put. Throttling set of paths so that the traffic can be distributed to other optimal paths are easy & proven in network management whereas they are not yet implemented in the freeways.

    Now that kind of feedback is coming through polling (of Television or Radio) basis and not pushed to node/packet.

    If realtime alert is given to people, even better, to cars (with wireless network) then congestion control will be much better.

    Coming back to your blog,
    Analogy is required to break down the complex ideas and then we can go back to actual problem to solve it without dilution.

    Madmax@
    IMO, you are over thinking this analogy.
    Mindframes is not trying to solve the traffic problem but correlates it to network issue.

    Even going into your theory, on a average people do the same thing again and again. People going in train is not going to decide to go by car or vice versa.

     
  8. BrainWaves

    December 21, 2007 at 8:46 pm

    Last comment was from me. (Brianwaves/Sriks)

    I used wrong login id I guess.

     
  9. Manohar

    December 21, 2007 at 9:01 pm

    @brainwaves:
    >Analogy is required to break down the complex ideas >and then we can go back to actual problem to solve >it without dilution

    I’m not sure I understand why an analogy is ‘required’. It may aid., but cant’ really be a requirement IMHO. Also is it possible that you are using the word ‘analogy’ instead of ‘example’?THe way I interpret it., an analogy is mappy the problem to a different but similar domain. An example is finding a particular instance of the problem in the same problem domain.

    But then again I dont’ think an example is a requirement to understand a complex problem either- though it might be highly beneficial.

     
  10. Mad Max

    December 21, 2007 at 9:49 pm

    @ Brainwaves: I understand dude and agree with your point..from a broad perspective you can probably say that one can think of Networking as a vastly simplified example of the traffic routing problem…I guess the reason why I think in this fashion is because my domain is social science…I had friends who worked in Transportation engineering and the bulk of their work was related to finding out how people behaved when “Stop” signs were placed at different points on the same intersection (among other human element issues).

    but personally…mixing science with social science is dangerous…i guess that is the problem with social scienctists… πŸ™‚

     
  11. Mindframes

    December 22, 2007 at 2:36 am

    @mad-max: Probably explains why engineers are not very social..;)

    Happy Holiday Season Everyone !!!

    (Am I self-contradicting my own theory…I dont know..:))

     
  12. Mad Max

    December 22, 2007 at 2:47 am

    @ Mindframes: hmm…i did not say that…all u guys are engineers and all are very social indeed…heheheh

    happy holidays to one and all again…

     

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: