How packet travels on network from source to destination

Journey of a packet in network

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

packet processing in network stack
  1. Application generates a packet to be sent on the network and send it to layer below.
  2. 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. 
  3. 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?)
  4. 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?)
  5. 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.

Processing a packet at router:

Router takes the packet and does three basic operations : Routing, forwarding and encapsulation

Routing

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.

packet routing : How packet travels



Forwarding

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.

Encapsulation
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.  
Processing packet at destination host

  1. Packet is received at network card, physical layer, which generates an interrupt to CPU and CPU reads packet in,
  2. 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.
  3. At IP layer, packet validation like checksum verification etc is done and then passed on to relevant transport layer.
  4. 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.

Process Vs Threads

Process Vs Threads

Process

In simple terms, any program in execution is called as process. Every process has a process state associated with it like memory, resources, code, data etc. In operating system, process has unique process identifier and associated process controller block (PCB). We will see in detail what PCB contains in later posts.


Process execution

Threads

Thread is an abstract entity which executes a sequence of instructions. Threads are light weight as compared to process, their creation is efficient and inter thread communication is fast as they use memory to communicate with each other instead of IPC. Process context switch is rather very expensive operation as compared to thread switches. Every program has at least one thread of execution.  A thread cannot live on its own, it has to be within some process. A process can have multiple threads.


Thread execution

From the definition we came across some differences. Let’s tabulate them.

Process vs Threads

Process
Threads
Can live on its own
Always runs in a process
All process have separate address space and stacks
Threads of a process share address space with each other. Threads have separate stack and registers as process has.
Inter process communication is done using IPC
Inter thread communication is done through shared memory.
Heavy weight in terms of IPC, context switch and creation
Light weight in terms of IPC, context switch and creation.
Process has data segment and heap of its own
Thread does not have them

There are two types of threads :
1. User space threads.
2. Kernel space threads.

Both have their own use and use case for using in a particular context.
User space threads are very fast in terms of create and switch. But they are not suitable when we need to do blocking I/O calls. Language level threads are best example of this kind of threads.

Kernel space threads are inefficient in terms of creation and switch but they do not block on system calls. These threads are scheduled using system scheduler as any normal process. Programmer does not have any direct controller over these threads.

There are models where one user thread maps to one kernel thread and one user thread maps to multiple kernel space threads or multiple user threads maps to one kernel space threads. These are termed as 
1: 1 Model
M: N Model
M : 1 Model

These models are realized using virtual processor (VP).  For first model, all user threads run in one VP.  In second model, user threads run in pool of VPs. This is default model.  While in third model, multiple user threads run in single VP.

In next post we would discuss POSIX library APIs for thread creation, execution and termination along with detailed look at process life cycle and structures used.

This post highlights key points of difference between process and threads, in future posts, we will understand more on these two concepts.