Data And Computer Communications - Network Layer

Network Layer

Network layer is concerned with getting packets from source all the way to destinations.

It is the lowest layer that deals with end-to-end transmission, and may make many hops at intermediate nodes.

• Internetworking - Link up different networks together
• Packetizing - Data are encapsulate into Packets
• Addressing - Identify destination and source in the network
• Routing - Link up multiple network together and decide the path
• Fragmenting - To divide the packet into smaller size

To conclude, The network layer is responsible for host-to-host data (packet) delivery

• Connect heterogeneous networks together to look like a single network (internetworking)
• Uniquely identity each device to allow global communication (addressing)
• Make decision to deliver data to the destination (routing)
• Fit data to the size used by the lower layer protocol (fragmentation)

Network-layer Services

Packetizing

At the Source Host:

• Receives the payload (data from the transport layer), add a header that contains the source and destination addresses and some other information
• If the payload is too large to fit into one datagram, the payload will be fragmented.

At the Destination Host:

• Receives the datagram from its data-link layer,
• decapsulates the packet and delivers the payload to the transport layer
• If the packet is fragmented, the network layer delivers the reassembled fragments to the transport layer until all fragments arrived.

Routing

The process by which nodes exchanges topological information to build correct forwarding tables.

As our Internet connects LANs and WANs with routers, there is more than one route from the source to the destination.

• The network layer is responsible for finding the BEST one among these routes.
• Routers uses routing protocols to derive its own routing table (forwarding table)

Use the Lowest Cost to form the route.

Forwarding

Normally, Forwarding means

• The operation of deciding the next-hop address (or output port) to forward to.
• The operation of moving a packet from an input port to an output port.

• When a router receives a packet from one of its attached network, the packet is forwarded to another attached network.
• Information in the packet header is used with the routing table to make this decision.

Forwarding table

For classless address, we need network address, address mask, IP address of the next router, and the interface number

• The network address and address mask are combined using the slash notation
• Forwarding table either show next-hop IP address, or show Interface

Error Control and Flow Control

Error Control

• There is only a checksum field in a datagram.
• The checksum field only check the header of a datagram.
  • For example, a corrupted destination address at the header will delivers the packet to a wrong host.

Flow Control

• The network layer does not provide any flow control
• Flow control is provided by the transport layer

Network Layer at the Source, Router, and Destination

Internet Protocol

IP is the network layer protocol on the Internet – i.e. IP is responsible to end-to-end delivery of packets

• IP provides a connectionless datagram service
• IP is an unreliable protocol providing a best-effort delivery service
• It does NOT guarantee a datagram will arrive in correct order
• It does NOT guarantee a datagram will arrive in certain time
• In fact, it does NOT even guarantee the datagram will ever arrive

Internet Protocol Version 4 (IPv4)

IPv4 Datagram Format

Header Fields(IP Header)

• VER - Version - currently 4 (for IPv4)
• HLEN - Header Length
  • Total header length = HLEN x 4 btyes
• Service type - Defining how the datagram should be handled by the routers
  • Precedence : 3 bits
    • Defining the priority of the datagram in issues such as congestion
    • At present, not used in version 4
  • service type : 4 bits (TOS bits)
    • With only one bit set at a time
  • Remaining bit : not used
• Total length (16 bits)
  • Length of the entire datagram, in octets (bytes)
• Identification (16bits)
  • Sequence number - together with addresses and protocol, it is used to identify a datagram uniquely
  • Used in reassembling fragmented datagrams
• Flags (3bits)
  • Used in fragmentation [X D M]
    • M - The “More” bit indicates whether this is the last fragment
    • D - “Don’t fragment” bit prohibits fragmentation
• Fragmentation offset (13bits)
  • Used in fragmentation, in units of 8 octets
• Time to live (TTL)
  • To ensure a datagram does not loop forever in network, the TTL field is decremented by one each time the datagram is processed by a router
  • When TTL reaches 0, the datagram is dropped
• Protocol
  • Next higher layer to receive data field at destination
  • Defined in RFC 1700, e.g. TCP = 6, UDP = 17.
• Header checksum
  • Verified by each router (usually discarded if error is found)
  • 16 bit ones’ complement sum of all 16 bit words in header
  • Must be recomputed by each router (because the TTL is decremented by 1, and other options field may have changed)
• Source IP address (32 bits)
• Destination IP address (32 bits)
• Options
  • Allows an IP header to be extended - in practice it is rarely used
• Padding
  • To fill the header to multiple of 32 bits long
  • Recall that the Header Length field is in units of 32 bits

Some Side Notes:

Default types for Some Applications in use of TOS

In practical case, TOS bits are ignored. Because there will be not much difference.

Identification , Flags and Fragmentation offset are used for Fragmentation.

Multiplexing and Demultiplexing using the value of the Protocol Field

Data Field (Payload)

• the transport-layer segment (TCP or UDP) (application data)
• other types of data, such as ICMP messages

Only IP Header is counted as Header.

The format and size of the received frame depend on the protocol used by the physical network

• MTU (Maximum Transfer Unit)
  • When a datagram is encapsulated in a frame, the total size of the datagram must be less than this maximum size

IP Fragmentation

• Each Interface has a Maximum Tranmission Unit (MTU)
• The MTU specifies the size of the largest IP packet
• Packets must be fragmented to be less than the MTU

• When fragmenting data, data are cutted in multiple parts then each fragmented data will add back the header.
  • We need to mark the fragmentation offset(8 bits) when dividing data
• When the fragmented data sent to the destination, the data will be reassembled.

Internet Protocols

The IP is mainly for forwarding the data, but in order to forward the packet we need support of other protocols.

We can roughly divide the protocols into 2 types:

• “Operational” protocol stack - related to the data movement
  • Protocols for moving bits and bytes (application, transport, network, data link)
  • Protocols for name/address mapping (DNS, ARP)
• “Configuration” protocols - related to the setup
  • Host auto-configuration (RARP, BOOTP, DHCP)
  • Routing protocols to configure forwarding tables (RIP, OSPF, IS-IS, BGP)

Internet Addressing | IP Addressing

• IP address: 32-bit identifier for host, router interface
• Interface: connection between host/router and physical link
  • router’s typically have multiple interfaces
  • host may have multiple interfaces
  • IP addresses associated with each interface

Number of Address space = $2^{32}$ > 4 billion

Hierarchy in Addressing

Similar to a telephone number which is divided into the country code, area code, …

IPv4 address is divided into two parts.

• Prefix (Netid) - define the network
• Suffix (Hostid) - define the node (or connection)

From IP Address Perspective, A network is:

• device interfaces with same network part of IP address
  • If network ID is the same, then we are within the same network
• can physically reach each other without intervening router

Classful Addressing

To accommodate small and large works, three fix-length prefix were designed.

• n = 8, 16, and 24

Example: Find the class of each address.

1. 00000001 00001011 00001011 11101111
2. 11000001 10000011 00011011 11111111
3. 14.23.120.8
4. 252.5.15.111

1 is Class A. (First bit is 0)

2 is Class C. (Frist three bit 110)

3 is Class A. (First byte 14)

4 is Class E. (First byte 252)

Classless Addressing

For classless addresses, we need to include the prefix length into the address notation (Slash notation)

The Prefix length determine the Suffix length, therefore determine the Number of address in the network.

• Number of addresses in the network $N = 2^{32-n}$, where n is the prefix length, and 32-n is the suffix length.

Address Mask

• Used to extract the network ID easily
• A 32-bit number
  • All prefix bits are set to 1s
  • suffix bits are set to 0s
• E.g. 10100111.11000111.10101010.01010010 or 167.199.170.82/27
  • The Address mask is 11111111.11111111.11111111.11100000 or 255.255.255.224

Using Address Mask to Extract Network Address

• The first address is used as the network address
  • Can easily be obtained by taking the AND of an address with the address mask

The 1st step of routing is resolving the network address from the destination address

• We need to use Network address to map with Interface

Block Allocation

The addresses are handled by Internet Corporation for Assigned Names and Numbers (ICANN).

ISP/Organization get addresses from ICANN

An organization (or an ISP) can further divide its network into subnetworks (subnets) and then assign addresses

Basic Rules:

• Number of allocated addresses $N = 2^{32-n}$, where n is the prefix length, and 32-n is the suffix length.
• The first address needs to be the prefix followed by (32-n) number of 0s.

Example:

Suppose that an ISP requests a block of 1000 addresses from ICANN.

Solution

• Since 1000 is not a power of 2, 1024 addresses are granted.
• The prefix length is calculated as n = 32 − log2(1024) = 22. An available block, 18.14.12.0/22, is granted to the ISP.
• The first address is 18.14.12.0.

Subnetwork

• An organization (or an ISP) can further divide its network into subnetworks (subnets) and then assign addresses

Basic Rules:

• Number of allocated addresses in each subnetwork is a power of 2,
  • i.e. $N_{sub} = 2^{32-ns}$, where ns is the prefix length of the subnetwork
• The first address needs to be the prefix followed by (32-ns) number of 0s. This can be achieved if we first assign addresses to large subnetworks.

Example

A Network consisting of three subnets

A Network consisting of eight subnets

Special Addresses

• This-host address – 0.0.0.0/32

  • Used when a host needs to send an IP datagram but it does not know its own IP address
  • to use as the source address
  • Used in DHCP

• Limited-broadcast Address – 255.255.255.255/32

  • Need to send a datagram to all devices in a network
  • The packet cannot travel outside the network (limited in local network)
  • Used in DHCP

• Loopback Address — 127.0.0.0/8

  • Use it as the destination address for program testing
  • The packet will not be outputted (just simulation)

• Private Addresses — 10.0.0.0/8, 172.16.0.0/12, 192.168.0.0/16, and 69.254.0.0/16

  • Create a network with the number of addresses much less than the actual available addresses
  • Only recognized by local device
  • Most common is 192.168.0.0

• Multicast Addresses — 224.0.0.0/4

• We can use Hostid All 0s to represent a Network.

• We can use Hostid All 1s can also represent a limited Broadcast address.

• We can use Netid all 0s to locate a particular host network.

• Loopback address

Address Aggregation

Address Aggregation is simply the reverse process in dividing large address into smaller address.

• Combine small network into larger network
• Look at IP of different subnetwork and find out the number of common bits

Simply find out the common number of bits in the network ID.

Example:

In the 4 Blocks, only 160.70.14. are the same. Therefore 24 common bits.

Dynamic Host Configuration Protocol (DHCP)

Normally, we can set the IP address of the device manually.

If we want to do it automatically, we can set up a DHCP server. when any host want to get the IP address, just send the request to the server.

DHCP is a protocol that permits a mobile or wired host to “dynamically” obtain its IP address from the network DHCP server when it joins a network, rather than from the network administrator.

The Device dont have IP address.

• DHCPDISCOVER
  • The device broadcast the message to ask if a server exists.
    • the device has no ip yet so Source Address is 0.0.0.0
    • the device does not know the location of Server so Destination address is 255.255.255.255
• DHCPOFFER
  • The server broadcast the offer to the device.
    • the server use its own ip as Source Address
    • the server use 255.255.255.255 as Destination address because the device has no ip yet
• DHCPREQUEST
  • The device make a formal request to the server for the use of IP address
    • the device use its given ip address to confirm the server
    • device still use 255.255.255.255 as Destination address because the given IP address was not confirmed
• DHCPACK
  • Server respond to confirm
    • the server use its own ip as Source Address
    • the server still use 255.255.255.255 as Destination address to make sure the device can receive to message.

After that, the device will start using the given IP address

The use of IP address will only valid in the given Lease time.

After Lease time end, the device need to refresh and send the request again for continuous using.

DHCP Message Format

How many DHCP server do we need?

We only need 1 DHCP Server in 1 Domain.

• We use Switches and a Router to forward the message to DHCP server.
• Network admin needs to connfigure the router to let the router know the IP address of the DNS server.

NAT (Network Address Translation)

In order to save the IP address, people use private address in forming local network.

• Then in order to get in touch with outside, a translation process is needed to convert private address into public address.
• NAT is doing this translation.
  • NAT router replaces the source address of all the outgoing packets by the global NAT address
  • NAT router replaces the destination address of all the incoming packets with the appropriate private address.

Translation Table of Incoming Packet Address

To translate the incoming packet address, we need a translation table to store the mapping.

Case I One global address

The translation table record down the destination address of all outgoing packets.

When the response come back from the destination, the router can find the private address of the packet from the source address of the packet.

Case II A Pool of IP Addresses

If we have a number of available IP address and also a number of hosts can access to the same outside site, we need the port to distinguish the private host.

Therefore in this case, port number is also stored.

Record both IP Addresses and Port Addresses using NAPT translation table

Network Address Port Translation (NAPT)

Show an example of Case II.

Routing at the Network Layer

In datagram approach, a packet is routed, hop by hop, from its source to its destination by the help of forwarding tables.

How Routing is done?

Routing is done by 2 Components.

• Control component (Control plane)
  • Decides where the packets will go
• Fowarding component (Forwarding plane)
  • Moving packets from input to output ports according to forwarding table and packet header

A Unicast IP Forwarding Algorithm

• First come First serve (FIFO)

Address Matching for Forwarding a packet

To forward a packet, we first need to perform Address Matching.

• Done by looking at the Longest prefix match (best matching)
  • Search from the Longest prefix
  • If F (Found), the packet will use that given Interface in the forwarding table.

Routing in the Internet

Since the internet is too big, we need 2 levels in routing.

The Internet consists of Autonomous Systems (AS) interconnected with each other.

• AS is a group of networks and routers under the authority of a single administration.
  • Just think of AS = A group of organization network. (e.g. a Provider network)

The 2-Level of routng:

• Interior routing (Intra-AS):
  • administrator responsible for choice of routing algorithm within network
• Exterior routing (Inter-AS):
  • routing between AS

Example: h1 want to send message to h2

Routing protocols of Intra-AS and Inter-AS

Routing protocol determines the path for a packet.

Intra-domain routing protocols (Interior routing):

• Routing Information Protocol (RIP) – based on distance-vector routing (RFC 1058)
• Open Shortest Path First (OSPF) – based on link-state routing (RFC 2328)

Inter-domain routing protocols (Exterior routing):

• Border Gateway Protocol Version 4 (BGP4) – based on path-vector routing (RFC 1772, RFC 1773)

Routing Algorithm

Routing Algorithm is the heart of any routing protocol.

Goal: determine “good” path (sequence of routers) through network from source to destination

“good” path typically means minimum cost path (other definitions are possible)

An internet can be modeled as a weighted graph.

• Route - node
• Each network between a pair of routers - edge
• There is a cost (weight) associated with each edge

We ignore the level 2 device because they just use to link up the routers.

To determine a path is based on some performance metrics, calculated based on one or several characteristics

• Hop count: the number of routers a packet must go through to reach a destination
  • The smaller the value, the better the path
  • Minimum-hop routing
• Weight of each link
  • The least weight (cost), better the path
  • Least-cost routing
• Other measure of the Cost
  • Bandwidth: the data capacity of a link
    • the cost of a link with higher data capacity (bps) is smaller
  • Delay: the time required to move a packet from source to destination
  • Reliability: the probability of failure

Routing decisions

Typically, Routing decisions should be made based on knowledge Information (Topology of the network, Traffic load and Link cost)

• Information should always keep up-to-date
• Update continuously Or Update when conditions change (depends on routing method)

Update more frequently provide better decision by consumes more network resources (bandwidth). Updates are treated as overhead.

We can use the different types of routing method/strategies:

• Fixed routing (Static Routing)
  • protocol are not used, set up routing table of the router manually by admin
  • we use it when the network is small
• Flooding
  • need not to know any information
• Random routing
  • need not to know any information
• Distributed routing
  • need to collect information from adjacent nodes
• Centralized routing
  • The central node makes use of information obtained from all nodes

Fixed Routing (Static Routing)

We simply preset route for each known destination network (default gateway is needed)

• Simple and Work well in a reliable network with a stable load
• If we have some changes in network topology, we need to change config of routers
  • Lack of flexibility and time consuming
• Do not react to network congestion or failures

Flooding

We simply flood the whole network.

• Very robust - All possible routes are attempted
• Requires no network information
• High traffic load - Large number of repetitive packets
  • traffic load is directly proportional to the network connectivity

Any router recieved packet will forward the packet to every neighbor routers (except the packet input router)

• Every incoming packet is copied to every outgoing link except the one it arrived on.
• This method guarantees that the packet reaches the destination in the shortest time.
  • Because every path is tried
  • every node can recieve the packet as well
• Eventually a number of copies will arrive at destination
  • Create too many copies might result in endless loops
  • To prevent infinite packets in circulation
    • Each packet is uniquely numbered so duplicates can be discarded
    • Nodes can remember packets already forwarded to keep network load in bounds
      • Make sure each router only forward once
    • Include a hop count / TTL in packets to limit the distance
• Used when we want to broadcast our information to all network
  • or Used for sending emergency messages

Example:

If we dont restrict, endless loop might happen or the node will recieve more than 1 copy.

Random Routing

We simply forward the packet randomly. (excluding the link on which the packet arrived)

• Robust and simple
• Requires no network information
• Less traffic load compared with flooding
• Performance not guaranteed (e.g., there is no upper bound in the number of hops from a source to a destination)

The outgoing link is chosen at random, excluding the link on which the packet arrived

To refine the random routing technique:

• Choose outgoing links in a round-robin fashion
• Or Select the link based on some predefined probability

Adaptive Routing (Dynamic Routing)

The routing decision will change as the network condition change (e.g. Failure link, Network congestion).

• Improved performance
• Aid congestion control

However:

• Requires info about network
  • Network information must be exchanged among the nodes
• Decisions are more complex
• Consume more computing power
• Increased network traffic due to the exchange of network information
  • Tradeoff between quality of the information and the amount of overhead
• Reacting too quickly can cause oscillation

Adaptive Routing includes:

• Distance Vector Routing
• Link State Routing
• Path Vector Routing

First we need to have the concept of Least Cost Tree.

Least Cost Tree is a way to present the least-cost paths.

Distance Vector Routing

• The router only exchange informations with the neighbor routers and build up the path

What is distance vector?

When a node is booted, it can only get the neighbors node information to create a initial distance vector. (e.g. A can only see B and D when booted, the initial distance vector only contain B,D and itself.)

After each node has created its initial vector, it send a copy of the vector to all its neighbors.

Then the distance vector is updated. After some changes, the complete distance vector is formed. Eventually, each node finds its least cost to other nodes.

Drawback of Distance Vector Routing:

• Decrease in cost propagate quickly
• Increase in cost propagate slowly
  • This problem is called “Count to infinity”.

Link State Routing

• Each node collect the cost of its connecting links
• Send its table to all other nodes

When a node is booted, it can only get information of its connecting links. (e.g. A can only see B and D when booted.)

Then the nodes send its table to all other nodes until every node can see the whole topology. (i.e. Each node has a gloabal picture about the network)

A Link state database is formed.

From the link state database we can draw the weighted graph topology.

Each node will then create a least-cost tree using the shortest path algorithm.

• Dijkstra Algorithm
• 1- The node choose itself as the root
• 2- Select one node, among all nodes not in the tree, which is closest to the root, and adds this to the tree.
• 3- After this new node is added to the tree, the cost of all other nodes not in the tree needs to be updated
• 4- Repeat step 2 and step 3 until all nodes are added to the tree

Distance vector routing VS Link state routing:

Distance Vector:

• View network topology from neighbors perspective
• Add distance vectors from router to router
• Frequent, periodic updates: Slow convergence
• Pass copies of routing tables to neighbor routers

Link State:

• Get common view of entire network topology
• Calculate the shortest path to other routers
• Event-triggered updates: Faster convergence
• Pass link state routing updates to all other routers

Path Vector Routing

Unlike link-state and distance-vector routing, path-vector routing is not based on the least-cost goal

• Based on the policy decided by Admin
  • E.g. Use minimum number of nodes to reach a destination and does not pass through node X as a middle node

It Path-Vector Routing, we create Spanning Trees.

When a node is booted, it creates a path vector based on the information it can obtain about its immediate neighbor. (e.g. A can reach A through itself, or reach B through A,B)

Then Each node sends its own vector to all its immediate neighbors, and Each node updates its own path vector.