Numpy for simulating a layer-2 switch

A layer-2 switch can be simulated using numpy! Surprised? You shouldn’t be, if you think a bit on what exactly happens in a switch.

Packets arrive and depart. How and when they depart, depend on the algorithm you use for switching. The question is how are packets, and their arrivals, simulated?

A packet as such, is nothing but a bunch of information. Every packet, at layer-2, has an associated port where it arrives (input port), and a destination port (output port) through which it goes out. Apart from this, a packet has an arrival time-stamp, that gives the arrival time of the packet. What else? Packet size; fine. So, for every packet, you generate arrival time, input port, output port, and packet size — thus, you generate a packet.

Since packets arrive at random time at a switch, we do not use a deterministic arrival process. Instead, we go for random arrival process. For example, Bernoulli process — you toss a coin at every fixed interval of time (say, time-slot), and if its a head, you generate a packet (information), or else you don’t. So, if you need to generate 100,000 time-slots, you toss coins for that many time-slots. Depending on the number packets you like to generate, you can set the probability. That’s simple right.

Other information, like packet sizes, are also taken from some distribution. Packet sizes in the Internet are known to follow a bi-modal uniform distribution. One mode is at 64-100 bytes, and the other around 1350-1500 bytes.

So, do you see how this can be done using numpy module in Python?

More, in a forthcoming post.

Mice and elephants in the Internet!

`The elephants in the Internet are the problem-makers. They are so bulky that they take up much of the things. Sometimes, they might also kill mices!’

So, what are these mice and elephants.

Well, the Internet traffic can be observed as packets. But, it can also be observed as flows (of packets). A flow can generally, not universally, be a file on your disk. So, when a video (file) is transferred from one machine in the Internet to your machine, it gets transferred as a `flow’ of packets (small data chunks, following some rules of the Internet). Studies reveal that if we take the entire traffic that goes through the Internet (or a subnetwork of the Internet) then, 80% of the traffic volume is contributed by 20% of flows. Its like saying that, 20% of Germans consume 80% of beer in Germany . Its actually true in the case of income distribution, to give a more correct example — 20% of people have 80% of the world’s income.

This is called the 80-20 rule, or the Pareto principle.

These 20% of flows that contribute to 80% of the traffic in volume, are called elephant flows. The others are mice. The mice flows are much larger in number, but they contribute to only 20% to the Internet traffic. Not surprising right — most of the time, when you browse through articles, blogs, facebook/orkut pages, etc., you end up downloading pages of very small sizes (mice), and that’s what you do most of the time, in between occasionally downloading a movie or so (elephant).

So, the Internet traffic basically consists of a few elephants and a large number of mice.

Adieu my friend

Upon earning his PhD title, he is going around the globe, hitchhiking. He starts the 2-3 years-journey today, heading towards south.

One of those who motivated me to go hiking in the alps, along with him. Two days in the alps, climbing to the top, finding a roof or putting up a tent to spend the night, cooking delicious French food, and then finally descending — typical nature of a trip — it was a completely different experience, as it was both tiring and refreshing! At the end of each trip, he would ask, `Will you join us again’. It was so much fun that, I said `yes’ 3-4 times that year.

`Wishing you a safe journey, and a journey filled with amazing moments of realizations. Adieu Ludo, hope to see you when you pass by India.’

PS: From Charmette trip:

Testing Ludo's `cool' attitude

LaTeX Math symbols, and Rubber

A good (and small) compilation of various math symbols and constructs available in LaTeX is documented here.

BTW, you should try out rubber, if you haven’t yet. It does enough number of compilations itself, to resolve reference issues. Makefile with multiple calls to latex and bibtex will suffice, but rubber in Makefile makes it faster and cleaner.

Happy new year!

Wishing everyone a wonderful year head.

And ..

.. please welcome my micro-blog.

Manipulating eps files

Sometimes, it is a little bit painful if you have to change something in a file with `eps’ format. One simple, but limited, trick is to edit the file manually using a text editor.

Fortunately, there exists a tool to convert eps files into different vector graphic formats, and most importantly to fig format. You can then edit the file using xfig. The tool is `pstoedit’. Pretty useful stuff.

Signing off.

“No scientific discovery is named after its original discoverer”

Says Stigler’s law.

Being an Indian, I quote a couple of interesting finds:

1) Leibniz formula for pi was discovered by an Indian Mathematician named Madhava (source wiki; related stuffs).

2) Jagadish Chandra Bose: The Real Inventor of Marconi’s Wireless Receiver (detailed info)

Curious to learn more in this line, I request the readers to add to this list, if possible. Thanks.

Switching — the functionality

Welcome back!

Tomorrow, I give a lecture on switch architecture. Coincidence, it should be — I have been drafting a post on the same topic, albeit intended for a more diverse set of audience (readers). So, here it goes.

The Internet we use is connected using nodes, called switches and routers. Switches are common — you might have seen it in your labs and/or hostels, or offices etc. Routers form the core of the Internet, connecting many networks. Both devices, switch and router, perform the basic function of transferring packets from incoming line to another outgoing line — called switching. With reference to the layered architecture, it comes in the layer two. So, every interconnecting node (be it a switch or a router) does the basic functionality of switching packets.

Now, how challenging is this?

Before answering this, a few bits of information. Each line brings in packets, and each line sends out packets, at a rate, say R. We call a line as input line, when it has incoming packet(s). A port is where a line and the switch interconnects. For every line, there is a corresponding port.

Consider the scenario of a switch that has just two lines. Then, the fabric inside the switch has very simple job to do — using some internal wires, keep the input and output ports connected forever!

Now consider another scenario. There are 100 lines connected to the switch. Since arrival of packets at ports are not deterministic, but random, there can be packets at some input lines, and none at others. In addition, the destination output port for each packet is also not deterministic. Input-output ports cannot be connected forever; but the connections should be made and torn down at the speed of packet arrivals. Therefore, to utilize the output line rate to the maximum, the switch has a complicated job to do: switch packets from input ports to output ports, such that maximum number of input-output pairs are selected. Given the input rate is fixed, we can be sure that not more than one packet can arrive at an input port in a time-slot (defined by packet_size/R). So, in one time-slot 100 packets can arrive at a switch; and each of them arrives at rate R. For maximum utilization, all these packets have to be switched within the same time-slot, yes, within the same time-slot; otherwise, packets will have be queued. More importantly, if the switching speed is slower than arrival rate, the packet queues will grow to infinite size! Therefore, a switch has to take the decision of which packets to transfer from which input ports and to which output ports, in one time-slot. If the number of ports (lines) is N, and the line capacity (rate) R, then the switch has to operate at a speed not less than R, using a matching algorithm which usually has its complexity a function of N. This is precisely the challenge faced by switches. This matching algorithm (in fact, this comes from graph theory) is equivalent to deciding where to put `0’s in an NxN matrix, such that, there is only one ‘0′ in each row and each column. The speed of electronics used in the switch fabrics is slow in the sense that, matching algorithms in the order of N are not scalable.

The above said story is the beginning of evolution of switch architecture. Now, we have switches that are scalable, thanks to the development of technology that has made distributed decision making within a switch a reality.

Cowards in a nation of braves

Thanks to E.P for the link to this good article.

The Pioneer > Online Edition : >> Cowards in a nation of braves

On the first anniversary of our victory in Kargil, there were official celebrations and the martyrs’ supreme sacrifice was recalled. By 2001, the then BJP-led NDA Government’s fervour had begun to taper off. A year later, July 26 was knocked off the calendar of national events as it was seen to be an obstacle on the path to peace! Since then, the day has come and gone, year after year, without the Government taking note of it in the mistaken notion that by doing so, it would keep the Pakistanis in good humour.

But even if cynical politicians and a callous Government fail to honour the memory of Captain Kalia and 532 other men who died in the Kargil war, should we the people of India forget them too?

The `small world’ fun

After a long time, I talked to Arathi, the day before yesterday; and yesterday, I met her ex-colleague, who was also our senior (at GEC) — I met Jiju. What made it really surprising was that, we met on a street corner at Aachen, in Germany! A nice pleasant surprise.

I am here for four days, attending (and presenting a work at) a conference.