Data Link Layer | Computer Networks - Computer Science Engineering (CSE) PDF Download


 An arbitrary collection of networks interconnected to provide some sort of host-host to packet delivery service

Data Link Layer | Computer Networks - Computer Science Engineering (CSE)

2. IP

  • IP stands for Internet Protocol
  •  Key tool used today to build scalable, heterogeneous internetworks
  • It runs on all the nodes in a collection of networks and defines the infrastructure that allows these nodes and networks to function as a single logical internetwork


Data Link Layer | Computer Networks - Computer Science Engineering (CSE)

IP Service Model


  • Packet Delivery Model
    • Connectionless model for data delivery
    • Best-effort delivery (unreliable service)
      • packets are lost
      • packets are delivered out of order
      • duplicate copies of a packet are delivered
      • packets can be delayed for a long time
  •  Global Addressing Scheme
    • Provides a way to identify all hosts in the network


Packet Format

  • Version (4): currently 4
  •  Hlen (4): number of 32-bit words in header
  •  TOS (8): type of service (not widely used)
  •  Length (16): number of bytes in this datagram
  •  Ident (16): used by fragmentation
  • Flags/Offset (16): used by fragmentation
  • TTL (8): number of hops this datagram has traveled
  •  Protocol (8): demux key (TCP=6, UDP=17)
  •  Checksum (16): of the header only DestAddr & SrcAddr (3


IP Fragmentation and Reassembly

  • Each network has some MTU (Maximum Transmission Unit)
    •  Ethernet (1500 bytes), FDDI (4500 bytes)
  • Strategy
    • Fragmentation occurs in a router when it receives a datagram that it wants to forward over a network which has (MTU < datagram) 
    • Reassembly is done at the receiving host
    • All the fragments carry the same identifier in the Ident field
    •  Fragments are self-contained datagrams
    •  IP does not recover from missing fragments
  • Data Link Layer | Computer Networks - Computer Science Engineering (CSE)

3. ARP


Address Translation Protocol (ARP) Map IP addresses into physical addresses

  • destination host
  • next hop router


  • encode physical address in host part of IP address
  • table-based

ARP (Address Resolution Protocol)


  • table of IP to physical address bindings broadcast request if IP address not in table target  machine responds with its physical address table entries are discarded if not refreshed


Data Link Layer | Computer Networks - Computer Science Engineering (CSE)

  •  HardwareType: type of physical network (e.g., Ethernet)
  •  ProtocolType: type of higher layer protocol (e.g., IP)
  •  HLEN & PLEN: length of physical and protocol addresses
  • Operation: request or response
  • Source/Target Physical/Protocol addresses.  
  • Ethernet addresses are configured into network by manufacturer and they are unique  IP addresses must be unique on a given internetwork but also must reflect the structure of the internetwork

 Most host Operating Systems provide a way to manually configure the IP information for the host. Drawbacks of manual configuration

  • A lot of work to configure all the hosts in a large network 
  • Configuration process is error-prune 
  • Automated Configuration Process is required


(RARP) is a Link layer networking protocol. RARP is described in internet EngineeringTask ForceETF) publication RFC 903. It has been rendered obsolete by the Bootstrap Protocol (BOOTP) and the modern Dynamic Host Configuration Protocol(DHCP). BOOTP configuration server assigns an IP address to each client from a pool of addresses. BOOTP uses the User Datagram Protocol (UDP)




  • DHCP server is responsible for providing configuration information to hosts
  • There is at least one DHCP server for an administrative domain
  • DHCP server maintains a pool of available addresses
  • Newly booted or attached host sends DHCPDISCOVER message to a special IP address (
  • DHCP relay agent unicasts the message to DHCP server and waits for the response



Data Link Layer | Computer Networks - Computer Science Engineering (CSE)


Defines a collection of error messages that are sent back to the source host whenever a router or host is unable to process an IP datagram successfully

  • Destination host unreachable due to link /node failure
  • Reassembly process failed
  • TTL had reached 0 (so datagrams don't cycle forever)
  • IP header checksum failed


  • From router to a source host
  • With a better route information



Forwarding versus Routing –  

Forwarding: – to select an output port based on destination address and routing table

Routing: –   process by which routing table is built


Forwarding table VS Routing table

Forwarding table: 

– Used when a packet is being forwarded and so must contain enough information to accomplish the forwarding function

– A row in the forwarding table contains the mapping from a network number to an outgoing interface and some MAC information, such as Ethernet Address of the next hop

Routing table

– Built by the routing algorithm as a precursor to build the forwarding table

–   Generally contains mapping from network numbers to next hops

– For a simple network, we can calculate all shortest paths and load them into some nonvolatile storage on each node.

–   Such a static approach has several shortcomings

–   It does not deal with node or link failures

–   It does not consider the addition of new nodes or links

–   It implies that edge costs cannot change

–   Need a distributed and dynamic protocol

–   Two main classes of protocols

–   Distance Vector

–   Link State


Distance Vector

  • Each  node  constructs  a  one  dimensional  array (a  vector)  containing the  “distances”
  • (costs) to all other nodes and distributes that vector to its immediate neighbors
  • Starting assumption is that each node knows the cost of the link to each of its directly connected neighbors
  • The distance vector routing algorithm is sometimes called as Bellman-Ford algorithm
  • Every T seconds each router sends its table to its neighbor each each router then updates its table based on the new information
  • Problems include fast response to good new and slow response to bad news. Also too many messages to update
  • When a node detects a link failure.· F detects that link to G has failed. F sets distance to G to infinity and sends update to A.  A sets distance to G to infinity since it uses F to reach GA receives periodic update from C with 2-hop path to G. A sets distance to G to 3 and sends update to F. · F decides it can reach G in 4 hops via A


Data Link Layer | Computer Networks - Computer Science Engineering (CSE)

Slightly different circumstances can prevent the network from stabilizing

  • Suppose the link from A to E goes down
  • In the next round of updates, A advertises a distance of infinity to E, but B and C advertise a distance of 2 to E
  • Depending on the exact timing of events, the following might happen 
    •  Node B, upon hearing that E can be reached in 2 hops from C, concludes that it can reach E in 3 hops and advertises this to A.
    • ·Node A concludes that it can reach E in 4 hops and advertises this to C
    • Node C concludes that it can reach E in 5 hops; and so on.

 This cycle stops only when the distances reach some number that is large enough to be considered infinite

 Count-to-infinity problem

 Use some relatively small number as an approximation of infinity.  For example, the maximum number of hops to get across a certain network is never going to be more than 16. One technique to improve the time to stabilize routing is called split horizon. When a node sends a routing update to its neighbors, it does not send those routes it learned from each neighbor back to that neighbor

 For example, if B has the route (E, 2, A) in its table, then it knows it must have learned this route from A, and so whenever B sends a routing update to A, it does not include the route (E, 2) in that update.  In a stronger version of split horizon, called split horizon with poison reverse. B actually sends that back route to A, but it puts negative information in the route to ensure that A will not eventually use B to get to E

 For example, B sends the route (E, ∞) to A

 Link State Routing

 Strategy: Send to all nodes (not just neighbors) information about directly connected links (not entire routing table).

  • Link State Packet (LSP) : id of the node that created the LSP cost of link to each directly connected neighbor sequence number (SEQNO)time-to-live (TTL) for this packet
  •  Reliable Flooding:  store most recent LSP from each node forward LSP to all nodes but one that sent it generate new LSP periodically; increment SEQNO start SEQNO at 0 when reboot decrement TTL of each stored LSP; discard when TTL=0




Global Addresses

  • Properties
    • globally unique
    • hierarchical: network + host
    • 4 Billion IP address, half are A type, ¼ is B type, and 1/8 is C type  Format
    • Dot notation

 IP Datagram Forwarding Strategy. every datagram contains destination's address if directly connected to destination network, then forward to host. if not directly connected to destination network, then forward to some router forwarding table maps network number into next hop each host has a default router. each router maintains a forwarding table


Example (router R2)

  • Algorithm

if (NetworkNum of destination = NetworkNum of one of my interfaces) then deliver packet to destination over that interface


if (NetworkNum of destination is in my forwarding table) then deliver packet to NextHop router


deliver packet to default router


For a host with only one interface and only a default router in its forwarding table, this simplifies to 

if (NetworkNum of destination = my NetworkNum)then deliver packet to destination directly


deliver packet to default router


10. CIDR

Classless Addressing

Classless Inter-Domain Routing:  A technique that addresses two scaling concerns in the Internet. The growth of backbone routing table as more and more network numbers need to be stored in them Potential exhaustion of the 32-bit address space

 Address assignment efficiency:  Arises because of the IP address structure with class A, B, and C addresses. Forces us to hand out network address space in fixed-size chunks of three very different sizes.  A network with two hosts needs a class C address. Address assignment efficiency = 2/255 = 0.78. A network with 256 hosts needs a class B address 


 Problem with this solution. Excessive storage requirement at the routers. If a single AS has, say 16 class C network numbers assigned to it, Every Internet backbone router needs 16 entries in its routing tables for that AS. This is true, even if the path to every one of these networks is the same If we had assigned a class B address to the AS.  The same routing information can be stored in one entry

 Efficiency = 16 × 255 / 65, 536 = 6.2%

 CIDR tries to balance the desire to minimize the number of routes that a router needs to know against the need to hand out addresses efficiently. CIDR uses aggregate routes Uses a single entry in the forwarding table to tell the router how to reach a lot of different networks.  Breaks the rigid boundaries between address classes

 Consider an AS with 16 class C network numbers. Instead of handing out 16 addresses at random, hand out a block of contiguous class C addresses Suppose we assign the class C network numbers from 192.4.16 through 192.4.31 Observe that top 20 bits of all the addresses in this range are the same (11000000 00000100 0001).  We have created a 20-bit network number (which is in between class B network number and class C number). Requires to hand out blocks of class C addresses that share a common prefix


Data Link Layer | Computer Networks - Computer Science Engineering (CSE)

The document Data Link Layer | Computer Networks - Computer Science Engineering (CSE) is a part of the Computer Science Engineering (CSE) Course Computer Networks.
All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)
21 videos|107 docs|66 tests

Up next

FAQs on Data Link Layer - Computer Networks - Computer Science Engineering (CSE)

1. What is the purpose of the Data Link Layer in computer networks?
Ans. The Data Link Layer is responsible for providing reliable transmission of data over a physical link between two network nodes. It ensures the error-free and sequential delivery of data frames and handles flow control, error detection, and error correction.
2. What are the key functions of the Data Link Layer?
Ans. The Data Link Layer performs several essential functions, including framing, error detection and correction, flow control, and addressing. It breaks the incoming data into frames, adds necessary control information, and reassembles the frames at the receiving end. It also checks for errors and ensures the data integrity during transmission.
3. What are the two sublayers of the Data Link Layer?
Ans. The Data Link Layer is divided into two sublayers: the Logical Link Control (LLC) sublayer and the Media Access Control (MAC) sublayer. The LLC sublayer handles error control and flow control, while the MAC sublayer manages the addressing and access to the physical medium.
4. How does the Data Link Layer handle flow control?
Ans. Flow control is achieved by the Data Link Layer through a process called sliding window protocol. It allows the sender to transmit multiple data frames without waiting for an acknowledgment for each frame. The receiver maintains a buffer to hold the received frames and sends a selective acknowledgment to the sender, indicating the next expected frame.
5. What are the common protocols used in the Data Link Layer?
Ans. The most common protocols used in the Data Link Layer are Ethernet, Wi-Fi (802.11), and Point-to-Point Protocol (PPP). Ethernet is widely used in local area networks (LANs), while Wi-Fi is used for wireless communication. PPP is commonly used for establishing a direct connection between two network nodes, such as a computer and an internet service provider.
21 videos|107 docs|66 tests
Download as PDF

Up next

Explore Courses for Computer Science Engineering (CSE) exam
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev
Related Searches



shortcuts and tricks


Sample Paper


Data Link Layer | Computer Networks - Computer Science Engineering (CSE)


Objective type Questions




Data Link Layer | Computer Networks - Computer Science Engineering (CSE)


Viva Questions


mock tests for examination


video lectures


study material




Important questions




Extra Questions


Data Link Layer | Computer Networks - Computer Science Engineering (CSE)


Previous Year Questions with Solutions


practice quizzes


Semester Notes


past year papers