Packet flow with multiples bridges & Routers

We have seen the packet flow when there are multiple bridges,  Now let us expand it bit more by adding one or more routers in between bridges and analyse the packet flow.

I have taken a basic example of two bridges and a router topology for connecting two nodes .

As we can see from above diagram Node1 is connected to Node2 via switch1-Router1-Switch2 . Both the nodes are in different network and hence we need a router to route packets .

To start with we assume Node1 & Node2 are just powered on and they do not have any information about connecting devices ( arp table is empty ).   Now a ICMP packet is being sent from node1 to node2 ( pinging 20.20.20.30 from node1 ) , let us analyse what happens while packet is being sent and received.

1. When an icmp packet gets trigger from Node1 , it checks the arp table entry for reaching the Node2. As it does not contain any arp entry for node2 it sends an arp request for finding the layer2 information of Node2 . In our case Node1 and Node 2 are not in the same network (which would be a basic L2 forwarding) and hence the arp packet would be sent on default gateway . ( if default gateway is not configured then Node1 cannot know where it has to send arp packet out).
2. Switch 1 will receive the arp request packet from Node1 . Now  Switch 1 will learn the mac entry corresponding to Node1 ,and creates /updates a mac entry corresponding to Node1.
3. Now switch 1 will forward the packet on to all of its interfaces except from which it has received the packet .In our case only one interface which is connected to router 1 .
4. When Router 1 receives the arp request , it checks in its route table if the destination ip address is part of its route table ( Either statically configured route entry or a dynamically learnt route) .
•  If Router1 finds the route entry corresponding to Node2 it gives reply to arp packet by providing its own mac address for reaching Node2.
•  If there is not route entry for Node 2 , the packet would be dropped and arp reply will not be sent .
5. The Arp reply sent by router 1 will be sent back to switch 1 , which intern will send it back to Node1 as it has learned the Node1 mac address during the arp request phase.
6. While sending the arp reply , Switch 1 will learn the mac address corresponding to Route 1 and creates/updates its mac address table.
7. Now since Node 1 has got the destination mac address to reach the Node2 ( strictly speaking it is the Router 1 mac address , how ever it is Router 1's job to take it further other side), it sends a ICMP request packet to Node2.
8. Since bridge1 has learned mac address of Router 1, it forwards the ICMP packet to the interface associated with Router 1.
9. When an ICMP packet is received at Router 1 , it checks if the destination ip address is its own ip address . If it is its own ip address it would send back the reply for ICMP packet.  In our case it is Node 2 ip address , it would keep ICMP packet aside and send an arp request for finding the layer2 mac address associated with Node2 ( Since it has got Route entry corresponding to Node2 ip address , it would know to which interface it should send the arp request).
10. Bridge 2 will learn the mac address of Router 1 and forwards the arp request on all of its interfaces except on the received interface (Similar to step 2 &3 ).
11. Node 2 would respond for the arp request , by providing its layer 2 information (mac address) to reach .
12. Bridge 2 would learn and update the arp entry for Node2 .
13. Now Router 1 will send the arp request which it kept aside by changing the destination mac address to the one it has learnt in step 11 and changing source mac address to Router 1's mac address.
14. Node 2 will respond to icmp request ( bridge 2 would have learnt the mac addresses of node 2 and router 1 by now as similar to step 2&3).
15. Once Router 1 gets reply for ICMP packet , it will alter the destination mac address to Node1's mac address ( ICMP echo Reply contains the mac address of Router1 from Node2) and source address as router1's mac address.
16. Bridge 1 will forward icmp reply to Node1 as it has updated its forwarding table while sending the icmp echo request .
17. Finally at Node1 , we will be having a reply for the ping request we have sent .

If we have multiple routers instead of Router 1 alone , at each router stage source and destination mac addresses would be changed similar to step 9 and 13 . And each router would send arp request for finding the next hop mac address at every stage and keeps it in its forwarding table.

Let us look into some other topic soon !

Source routing .

Usually routing is performed at the routing device ( network routing ) , to send the packet to a destination based on various routing decisions & routing protocols .

Where as in Source routing the sender would mention the route the packet must take to reach the destination . The router present in the network path, will simply forward the packet based on the routing path mentioned. 

We have two types of source routing techniques .

• Strict source routing 
• Loose source record route (LSRR)

In strict source routing , the sender determines the exact route the packet must follow to reach the destination . This type of source routing is generally not employed .

In LSSR  , the sender would mention one or more hops the packet must go through to reach the destination .

The main usages of source routing techniques are for 

• performance improvement 
• trouble shooting.

Understanding spanning tree !

Let us look into all important protocol of Layer 2 , which is spanning tree protocol . As we have seen in bridging loops article , it is understood that redundant topology and bridging loops coexist together unless we have some mechanism to avoid loops .

The mechanism is nothing but running a spanning tree protocol which will make sure to avoid loops and switches to redundant path during a failure.

Let us dive into the protocol and analyse how it exactly does this job for us .  I have created a following topology for understanding the protocol .

As we can see from the diagram, i have created a topology which has got multiple paths to reach a particular node . 

For example to for bridge 1 to reach bridge 4  , it can reach via bridge 1-bridge 3 -bridge 4   (or) bridge 1-bridge 4 (or) bridge 1 -bridge 2- bridge 4

Same is the case with other bridges . So in these type of topologies we must disable/shut down the ports which might causes loops.  Thankfully we have spanning tree protocol which takes cares of all such issues for us otherwise life would have been hell for network administrators !

If you observe in the picture, i have mentioned the mac address and priority of each of the bridges which are one of the key factors in spanning tree . 

The key steps in spanning tree protocol are .

• Find out the root bridge,
• Find the root ports 
• Find the designated ports 

To start with , All the nodes think they are the root bridges . Hence all the bridges participating in spanning tree will send STP (bridge protocol Data units) BPDUs out towards connected bridges.  

The BPDU format is as below

Protocol Identifier	2 (bytes)
Version	1
Message Type	1
Flags	1
Root ID	8
Path Cost	4
Bridge ID	8
Port ID	2
Message Age	2
Maximum Time	2
Hello Time	2
Forward delay	2

Considering the complexity of all the parameters , We will limit ourselves to Parameters which are relevant during convergence of a STP . I will present the complete BPDU details in a separate article.

Now coming back to election of root bridge ,  Since all the bridges are sending BPDUs each of the bridge ports will also receive BPDU from its adjacent bridge ports . The bridge will keep a "best" BPDU and discard the rest of the BPDU  , the  "best" BPDU is decided on the following criteria .

• Lowest root bridge ID ( bridge priority + MAC address )
• If Root IDs are equal , it will start checking for Lowest path cost  ( Cumulative cost of links between switch and root bridge)
• If the Path costs are equal ,Lowest sender bridge ID 
• If the Sender bridge IDs are also equal ,  Lowest sender port ID  (Port priority + port number)

Once the root bridge is decided based on the above election criteria , Now its turn for deciding the port roles .

• Root port - Every non root bridge must select the root port , the port which is closest root port (based on path cost )
• Designated port -  Ports providing the least path cost from the segment to root bridge , have to be decided . The bridge containing designated ports for a given segment is called designated bridge .
• Ports which are neither root port nor designated ports are put into blocking state ( Non designated ports).

If a bridge receives a better configuration that it would transmit , it would stop sending the configuration messages . Hence once the algorithm stabilizes only one bridge per LAN i.e. designated bridge for that LAN will send configuration messages. 

When a failure happens in any of the ports i.e designated bridge stops sending BPDUs for a period about max age time , Non designated bridge will turn the blocking port to forwarding state enabling packet transmission via that port .

After converging , the entire topology might look like below . It is not the only way it could converge , but depends on the selection criteria logic it could change accordingly .

Now we know the STP selection criteria , we will try to come up with state diagram of the STP by considering various stages during election process .

• Blocking  - The switch will go into blocking state when it receives a better path to root bridge Or a port is not a root port or designated port . During this state switch will not forward packets and discards frames it receives on its ports  . This time is normally 20 seconds.
• Listening  - After blocking state the root port or designated port will move into listening state. In this states , switch will not forward packets and discards the frames received from another segment for forwarding .It will accept BPDUs and gives it to switch module for processing. This time period is normally 15 seconds.     
• Learning  -  In this state switch starts learning the mac address from the received frames , but it will not forward frames in this state .  This time period is normally 15 seconds.
• Forwarding  - In this state, switch will start forwarding frames learns mac addresses of the received frames .
• Disabled  - The ports which are not participating in STP will be put into this state.

As we have seen how the topology got converged and states present in the STP , we should by know understood the time it takes for moving from one state to another is huge. So based on this time it will try to converge when there is a failure.  

There are some changes done in the STP to fasten the process and not loose the advantage of STP . We shall look into such things in the next article .

Bridging loops ..

As we have learned from the basic concept of bridges, what is a transparent bridge . From this understanding we will go one step ahead and find out what are bridging loops.

In any topology we would love to have redundant paths to reach  any destination so that during failure of one path , it seamlessly switches its direction and  chooses another path . 

In a bridged LAN environment, where we have multiple paths bridging loops will exists and drain the network bandwidth by continuously looping the packet around . Let us first see how it actually happens.

  

In the above picture, we see there are two bridges placed for connecting station 1 from network segment 1 to station 2 in network segment 2 . 

Let us imagine both the bridges forwarding table entry is empty and we get a packet from station 1 destined towards station 2.

•            Since both the bridges are in promiscuous mode , both will receive packet in segment 1 , destined to Station 2 .  Now since they are transparent bridges , they will learn that station 1 can be reached  via port connected to segment 1 .         
•             Both the bridges will now plan to send the packet out on all other interfaces except on the received port, as they do not have any entry for reaching station 2 .
•             Since only one bridge can transmit packet out any point of time ( because of CSMA/CD or any other layer 1 protocol), assuming bridge 1 will get time slice for sending packet . This packet will be received by station 2 as well as bridge 2. 
• Now bridge 2 thinks that station 1 has moved its position from segment 1 to segment 2 , it will alter its forwarding table accordingly .
• When bridge 2 sends packet out once its get time slice , Along with  station 2 , bridge 1  will also receive the packet. Now imagine station 2 behavior , it has received same packet twice from two different points - whose behavior is unpredictable here !!
•  Since bridge 1 also received the packet  from bridge 2 , it alters its own forwarding table thinking that station 1 has moved it position from segment 1 to segment 2 .
• Every time a packet is generated , it loops around the paths continuously and bridge forwarding entries will flap every time . Imagine a case when you send a broadcast packet from station 1 / station 2 . 
• This is mere example of what could happen if we have multiple paths , in real life scenario situation is much worse , each of stations will have multiple paths in various segments . 

To avoid loops , we need to run a protocol on the bridges which can determine a possible loop and shuts down one of the ports of the bridges ( logically !! )

Lets look in to such protocol in the next article , which is "spanning tree protocol "

Packet forwarding in bridges

Before we start learning about how bridges forward the packets , we need to first understand what is "transparent bridging".

Transparent bridging: From the name we can try to imagine what would be the functionality of these type of bridges. They tend to be transparent to network -meaning their presence and operation is transparent to hosts . These bridges will learn the locations of the hosts connected by analyzing the source address of the incoming packets.

For example : if a bridge receives packet from Host A on Port 1 , it will conclude and in its data base that "Host A can be reachable via Port 1 "

Now that we have understood the basic concept of transparent bridging , let us try to use it for understanding the packet flow among bridges.

	Case 1 : Single bridge multiple hosts

Assume Bridge forwarding table is empty .

When Host A tries to send packet to Host D ,

• It learns the source address , and adds in its forwarding table.
• The Bridge checks for destination port based on destination address , Since it does not have any entry corresponding to Host D it forwards packets to all of the ports (except on port where packet has been received).
• All the ports receive the packets but since it is not intended for that hosts , All the ports silently discards the packet except Host D.
• Now , when Host D wants to send a packet to Host A , bridge would directly send on to port connected Host A as it has got entry corresponding to Host A .

Case 2 : Multiple Bridges, Multiple hosts 

As described in the above diagram , now we have two bridges Bridge 1 & Bridge 2 connected to each other and each has got three hosts connected on different ports .

• When Host A wants to send packet to Host F , Bridge 1 will see its own forwarding table and do not find it there , Hence it forwards the packet to all of its connected ports including port 1 to which other bridge is connected . 
• Bridge 2 receives the packet and "learns" that Host A is reachable on its port 2 ( even though there is a different bridge connected to port 2 , for bridge 2 it does not matter ! ) 
• Bridge 2 forwards the packet to all of its ports and Host F also receives the packet .
• Now when host F wants to send packet back to Host A  , Since Bridge 2 has already got information about Host A ( reachable on port 2 ) it just forwards the packet on to port 1 
• Since Bridge 1 has already learnt about Host A location , it forwards the packet to port connected to Host A .
• Once all the hosts start sending some packets  , both the bridges would have learned about the all the Hosts connected .

Looking from Bridge 1 point of view , the forwarding table would be some thing similar to below 

Similarly from Bridge 2 point of view , it looks like some thing like this 

 I have tried to put down my thoughts  about the bridge learning and how it forwards the packet in a simpler way , not to complicate things !

I shall take you to next step , which is bridging loops and how to avoid them !