Packet routing:Journey of a packet in internet
I am digressing from my topics algorithms and operating system because this question is now a days is commonly asked in interviews. More so in any networking related companies interviews like CISCO, Juniper, ALU and Qualcom. Question is how does a packet travels from source to destination in internet. This is to gauge if you understand packet routing.
There are three parts to the question. First is what happens inside the computer or host when a packet is generated by application. Second part is how it travels from one host that is source to other host that is destination with many routers sitting in between. Third part is what goes inside destination host when it receives a packet on network. We will discuss each one by one.
Processing packet at source machine:
Below figure explains above steps a packet goes through before going out of host
- Application generates a packet to be sent on the network and send it to layer below.
- The next layer is called as transport layer which manages end to end communication between two machines. The protocol used can be TCP or UDP. What is difference between these two protocol is another subject altogether.
- Once packet is formed at transport layer, it is sent to network layer which adds source and destination IP in the packet.Most important field which is added at IP or network layer is Time To Live (TTL) which is used by intermediate routers/switches to decide if packet needs to be forwarded or not. (How destination IP is found?)
- After network layer, packet reaches data link or MAC layer, where source and destination MAC address of machines are added. We will see how these fields change between every two neighbors. (How destination MAC is found?)
- Data link layer push this packet to physical layer where it is sent as stream of “0” and “1” on physical medium available.
There are lot more things being done at each layer like MTU decision at transport, fragmentation at IP and data link layer etc, but for simplicity of explanation, I have skipped them.
Now packet has reached at an intermediate router which sit between source and destination like shown in figure.
Router takes the packet and does three basic operations : Routing, forwarding and encapsulation
When router receives packet, first of all it strips down the MAC layer header and looks into the IP header which contains destination IP address. Once destination IP is known, router looks into it database in order to find where should this packet be forwarded to make it reach to destination. This databases is known as routing table.
There are three cases which may occur when router looks into routing table for destination IP
1. If there is an entry corresponding to destination IP, we receive the interface name the packet should be forwarded on to.
2. If there is no direct entry, then IP is converted into network IP using mask and then checked again.It should be noted that longest prefix match to be find best forwarding interface.
3. If nothing matches, then router just forwards it to default destination configured.
Once routing process finishes, the packet is switched from the ingress interface to egress interface, commonly known as forwarding. Process switching, fast switching and CEF switching are three method of forwarding.
Before third step, router decreases the TTL and recalculates the checksum of packet and put it back.
Third process is encapsulation. Please keep in mind that L3 or layer 3 or network layer destination IP address never changes through out the path of IP packet, except from cases like NATing or VPN.
Only thing which changes is source and destination MAC addresses at data link layer.
Router caches the MAC address of next hops it needs to send packet to, it replaces the source and destination MAC address in it and send it to physical layer.
Below figure explains packet transformation between ingress and egress interfaces.
- Packet is received at network card, physical layer, which generates an interrupt to CPU and CPU reads packet in,
- At data link layer, destination MAC address is checked to see if packet is destined to this machine, If yes, packet is sent up to network layer.
- At IP layer, packet validation like checksum verification etc is done and then passed on to relevant transport layer.
- Transport later then passes it on to the appropriate port so that it reaches correct application.
I have explained the process without going into too much of details deliberately to make it easy to understand the essential process without worrying about finder details. Please share your views if you have something to add or I have missed something important. I would also love to learn about other good sources writing on similar topics, please share them in comments.