Pick your Look: Standard - Rising Blue - Retro Curves
RajeshGoli.com
- Thoughts on Technology and life...
Technology :: Networking: To route or to switch..
If you have heard the terms routing and forwarding but are not sure of what they actually mean, or if you don't understand the difference between them, then this article is for you. Without further ado, I will dive into this most fundamental of concepts in networking.
Routing :
IP packets are routed and forwarded using the routing paradigm. In this paradigm, the data traveling as packets has the destination address stamped into each packet. The router, on getting a packet examines the destination address and decides which of its adjacent routers may be able to reach the destination and hands over the packet to that router.
Routing is usually done using lookup. Each router has a forwarding table. The forwarding entry consists of (destination address, next router in route to that destination) tuples in the simplest case. The router tries to find the destination address in the forwarding table. If it does find the address, it will then hand over the packet to the next router in route.
If we assume the forwarding table to be a sorted array of destination addresses, then the time taken by each lookup will be of order O(log(n)), where n is the number of addresses in the forwarding table. On a router that can route to 2^16 destinations, this time is of order of O(16). If we consider the fact that lookup has to be done on each and every packet, this time is not an impressive time frame. Moreover, updating this kind of table will take O(2^16), which is prohibitively expensive.
By using a balanced binary tree we can get lookup and updating speeds of order O(W), where W is number of bits in the address, i.e., O(32). With the assistance of some expensive hardware we can bring the speed to an order of ~O(1).
It is clear from the preceding discussion that for forwarding large amounts of data routing is not the best of the options. Lets explore the alternative.
Forwarding :
Let us consider a setup as shown in the diagram. Here, A,B,C and D are “switches” they have basic ability to switch traffic from one interface to other. An interface is an incoming or an outgoing connection from a switch. Let every switch be able to uniquely identify its interfaces i.e. each switch labels its interfaces with identifiers. Thus A calls its incoming interface as 1 and outgoing interface as 2. B calls its incoming interface as 1 and outgoing interfaces as 2 and 3 and so on.
Let us assume that we have a requirement to pump data from A to C. We shall see a very simple method of doing this. We go to A and program it to send out all the data coming on interface 1 to interface 2. We go to B and program it to send all the data coming from interface 1 to interface 2. Again, in C we program everything coming from interface 1 to go to interface 2. We have, in effect created a wire or a circuit from A to C. The Pseudo-circuit is highlighted in the diagram below.
How will this work internally for the switch? The switch will have (Incoming interface, Outgoing Interface) tuples stored in an array with incoming interface as index. When a packet comes on interface 1, the switch will just look Array[1] to find the outgoing interface and put that packet on that interface bound to next switch.
This approach works, but it isn’t very novel. As the reader must already have been wondering, we are ill equipped to switch some data to C and some other data to D. Let us now consider the case where some of the data from A is bound to C and some other data is bound to D.
The dotted lines are virtual interfaces. They do not exist in reality, but we will act as though they were real interfaces with associated numbers. Now, if we send all the traffic bound to C on virtual interface 1 and all the traffic bound to D on virtual interface 2, our job becomes easy. We will now program A such that all data coming on virtual interface 1 goes to virtual interface 3. For switch B, this tuple will be (1,3) and for C this tuple is (1,2). We can similarly program all the switches such that all data coming on virtual interface 2 on A will go out on virtual interface 2 on D. We have in effect created two virtual circuits, one from A to C and one from A to D.
There are some issues that we have not taken notice of yet. The first issue is how do we know which virtual interface a packet is coming on? Since there can be more than one virtual interface on a single physical interface, the switch cannot automatically infer this information. The solution to this is put the virtual interface ID in the header of the packet. It must be clear from the above discussion that Virtual Interface ID must be unique to the switch and would be of only local significance i.e. a virtual interface ID has no global significance and can be reused across switches.
How does it work for the switch? It will again have a (Incoming interface, Outgoing interface) tuple. But this time this tuple will also contain the virtual interface of the next switch that this packet needs to go i.e. the tuple will now be (Incoming virtual interface, Outgoing virtual interface, Incoming virtual Interface for the next switch). The switch will always replace the existing interface number in the packet header with the one that the next switch in line expects. This operation is a simple O(1) operation for the switch. It is much faster/cheaper than routing when a large amount of data is in transit.
Created on 25th July 2005
- There were some errors in your input
Add Article Comment
Articles
Portfolio
Styles
Support this site!
