Network Layer: IP, Routing Protocols

• These notes cover the network layer, including introduction, virtual circuit and datagram networks, the inside of a router, the Internet Protocol (IP), and routing algorithms like Link State (LS), Distance Vector (DV), and Hierarchical Routing.
• It highlights how the transport layer relies on the network layer for host-to-host communication.
• The network layer, unlike transport and application layers, exists in every host and router, making it complex.

Introduction to the Network Layer

• The network layer in a host encapsulates transport layer segments into datagrams.
• Datagrams are sent to the nearest router and the roles of routers primarily involves forwarding datagrams from input links to output links.
• Routers lack upper layers (application and transport) as they do not run those protocols.
• The network layer's main job is to move packets from a sending host to a receiving host.
• Forwarding occurs when a router moves a packet from an input link to the correct output link.
• Routing involves determining the path packets take from sender to receiver with routing algorithms calculating the best routes.
• Routers have forwarding tables.
• Routers forward packets by examining a header value in the packet, using it to find the correct entry in the forwarding table.
• The forwarding table entry shows the outgoing link interface for the packet's next hop.
• Header values can indicate destination address or connection, depending on protocol.
• Connection setup involves routers along a path handshaking to establish state before packets flow.

Network Service Models

• The transport layer passes packets to the network layer, and the network layer offers services like:
  • Guaranteed delivery of packets.
  • Guaranteed delivery with bounded delay, ensuring delivery within a specified time.
  • In-order packet delivery with packets arriving in the order sent.
  • Guaranteed minimal bandwidth, emulating a transmission link with a set bit rate.
  • Guaranteed maximum jitter, ensuring consistent packet timing.
  • Security services using encryption and authentication with a shared key.
• The Internet provides a best-effort service.
• ATM offers multiple service models, including constant bit rate (CBR) and available bit rate (ABR).
  • CBR provides a virtual pipe with fixed bandwidth.
  • ABR offers a slightly better-than-best-effort service, providing feedback on congestion.

Virtual Circuit and Datagram Networks

• The network layer provides connectionless or connection services between hosts.
• Unlike transport layer services, network layer services are host-to-host while transport layer services are process-to-process.
• Virtual-circuit (VC) networks provide a connection service, while datagram networks provide a connectionless service.
• Virtual circuits (VCs) are network-layer connections which consist of:
  • Path: A series of links and routers between hosts.
  • VC numbers: One number for each link along the path.
  • Forwarding table entries: One for each router along the path.
• Packets in a VC carry a VC number in their header, and routers replace this number at each link.
• VC networks maintain connection state information, adding entries when connections are made and removing them when released.
• Three phases in a VC:
  • VC Setup: Sender contacts network layer, specifies receiver, and sets up VC.
  • Data Transfer: Packets flow after the VC is set up.
  • VC Teardown: Sender or receiver ends the VC.
• The network layer informs end systems of call termination and updates forwarding tables.
• Signaling messages are used to initiate or terminate a VC.
• Datagram networks stamp packets with the destination address and send them into the network.
• Each router uses the destination address to forward the packet using a forwarding table.
• Routers match a prefix of the packet's destination address to entries in the table.
• If multiple matches are found, the longest prefix matching rule is used with forwarding to the associated link.
• Forwarding tables in datagram networks can be modified, allowing packets to take different paths and arrive out of order.

Inside a Router

• A router's architecture includes input ports, output ports, a switching fabric, and a routing processor.
• Input ports perform physical and link layer functions, and importantly, the lookup function using a forwarding table.
• The switching fabric connects input to output ports with it contained within the router.
• Output ports store and transmit packets, performing link and physical layer functions.
• The routing processor runs routing protocols, maintains routing tables, and computes the forwarding table.
• Input ports, output ports, and the switching fabric implement the forwarding plane.
• Control plane functions execute on the routing processor.
• Input processing involves line termination, link-layer processing, and lookup to determine the output port.
• The forwarding table is computed and updated with a shadow copy at each input port.

Switching Fabrics

• Switching fabrics forward packets from input to output ports: • Switching via Memory: Early routers used direct CPU control, but it's limited. • Switching via a Bus: Input ports transfer packets to output ports over a shared bus (prepending an internal label), but only one packet can cross at a time. • Switching via an Interconnection Network: More sophisticated, like a crossbar switch with 2N buses connecting N input and output ports and controlled by a switch fabric controller.

Output Processing

• Output port processing selects, de-queues, and transmits packets, performing link and physical-layer functions.
• Packet queues form at input and output ports depending on traffic load, switching fabric speed, and line speed.
• If queues grow too large, packet loss occurs.
• Packet scheduling at the output port selects which packet to send, with options like first-come-first-served (FCFS) and quality-of-service guarantees.
• Active queue management (AQM) algorithms drop or mark packets to manage congestion.

Input Port Queuing

• Input port queuing occurs if the switch fabric isn't fast enough which results in head-of-the-line (HOL) blocking, where a packet is delayed because another packet ahead of it is blocked.

Internet Protocol (IP): Addressing and Forwarding

• The Internet's network layer has three main parts: IP protocol, routing component, and error reporting.
• Key fields in the IPv4 datagram include:
  • Version number: Indicates IP protocol version.
  • Header Length: Determines where data begins due to variable options.
  • Type of Service: Indicates how the network should handle the IP packet.
  • Datagram Length: Total length of the IP datagram.
  • Time-to-Live: Prevents datagrams from looping forever.
  • Protocol: Indicates the transport-layer protocol.
  • Header Checksum: Detects bit errors.
  • Source Address: Sender's IP address.
  • Destination Address: Receiver's IP address.
  • Options: Allows extending the IP header.
  • Data: Transport-layer segment.
• IP datagram fragmentation divides data into smaller pieces for transmission, with each fragment reassembled at the destination with Identification, Flag, and Fragment offset fields which are in the datagram header.

IPv4 Addressing

• Interfaces, not hosts/routers, have IP addresses.
• Dotted-decimal notation is used to represent IP addresses (e.g., 193.32.216.9).
• Each interface must have a globally unique IP address.
• Interfaces connected to the same subnet share a common IP address prefix.
• Addresses are assigned to subnets using notation like 223.1.1.0/24, where /24 indicates the subnet mask.
• Classless Interdomain Routing (CIDR) is the Internet’s address assignment strategy.
• CIDR uses a.b.c.d/x, where x is the number of bits in the prefix.
• Older classful addressing used 8, 16, or 24-bit subnet addresses (class A, B, C).
• 255.255.255.255 is the IP broadcast address.

Obtaining and Managing IP Addresses

• Organizations obtain IP addresses from their ISP.
• IP addresses are managed by the Internet Corporation for Assigned Names and Numbers (ICANN).
• Dynamic Host Configuration Protocol (DHCP) dynamically assigns IP addresses and allows hosts to learn subnet mask, default gateway, and DNS server.
• Steps in DHCP protocol:
  • DHCP server discovery done via a DHCP discover message broadcast to port 67.
  • DHCP server offer with a DHCP offer message announcing IP address to use and is broadcast to all nodes on the subnet.
  • DHCP request is a the client responds to a server offer message.
  • DHCP ACK confirms parameters after the new IP address is assigned for the duration of the lease time.

Network Address Translation

• Network Address Translation (NAT) allows multiple devices to share a single public IP address by translating local IP addresses to a global IP address.

Internet Control Message Protocol (ICMP)

• ICMP is used by hosts and routers to share network-layer information.
• ICMP messages include type and code fields with some ICMP message types include: -Echo Reply (to ping) -Destination Network Unreachable -Source Quench (Congestion Control) -TTL Expired
• The TTL expired message is used in traceroute to identify routers along a path and involves sending packets with increasing TTL values.

IPv6

• IPv6 includes expanded address space (128 bits), streamlined 40-byte header, and flow labeling.
• The size of the IP address increases from 32 to 128 bits.
• IPv6 address guarantees the world won't run out of address.
• The Version, Traffic Class, and Hop Limit fields are defined and used with Traffic Class is similar to IPv4 Type of Service.
• Flow Label, Payload Length, Next Header, Source Address, and Destination Address also provide additional information.
• Transitioning from IPv4 to IPv6 involves a dual-stack approach, or tunneling, where IPv6 packets are put inside IPv4 packets.
• Routers in a tunnel route packets as they would any other datagram.

Routing Algorithms

• A routing algorithm finds the best path for data packets.
• The job routing is to find good paths from senders to receivers, through the network of routers.
• Packets move through a sequence of routers from source to destination along determined paths.
• Default routers forward packets and graphs represents various routing problems.
• G = (N,E) defines nodes and edges and the nodes in the graph represent routers, the edges represent links.
• The edges have weights to calculate the optimum path.
• Least cost paths contain of nodes or routers through which the moving packet travel from source to destination with minimum cost.
• Classification of Routing Algorithms considers global/decentralized, static/dynamic, load sensitive/load insensitive.

Types of Routing Algorithms

• Global routing computes the least-cost path with complete network knowledge. • These types of algorithms are referred to as link-state algorithm
• Decentralized routing uses iterative, distributed calculation. • These types of algorithms are referred to as distance vector (DV) algorithm.
• Static algorithms route change slowly over time with manual configurations and manual editing of tables.
• Dynamic routing adapts to network traffic or topology changes and can be run periodically or in response to changes.
• Load-sensitive algorithms have link costs that reflect current congestion and tend to avoid congested routes.
• Load-insensitive designs do not explicitly consider current congestion.

Link State (LS) Routing Algorithm

• Finds the shortest path from a source to all other vertices.
• Link-state algorithms use the network topology and link costs as input and accomplished by having each node complete a link-state broadcast algorithm.
• Dijkstra's algorithm finds least-cost paths in iterations.
• Definitions for Dijkstra's algorithm include:
  • D(v): Cost of the least-cost path from the source node to destination v as of this iteration of the algorithm.
  • P(v): Previous node (neighbor of v) along the current least-cost path from the source to v.
  • N': Subset of nodes. v is in N' if the least-cost path from the source to v is definitively known.
• The cost to w is set to 5 since this is the cost of the direct (one hop) link from u to w.

Distance Vector (DV) Routing Algorithm

• DV algorithm is iterative, asynchronous, and distributed.
• Achieves distribution in which each node receives some information from one or more of its directly attached neighbors.
• Iterative processes continue until no more information is exchanged between neighbors.
• Asynchronous features do not require all of the nodes to operate in lockstep with each other.
• Definition of d x (y): cost of the least-cost path from node x to node y.
• Then the least costs are related by the celebrated Bellman-Ford (dx (y) = minv {c(x,v) + dv (y)}.
• DV algorithm maintains information for each neighbor, including the cost from x to v and the distance vectors of each neighbor.
• Processes include updates for routing tables from what is received in the various update messages from adjacent nodes.
• Problems include the "count-to-infinity" problem, and updates will be slow if various hops continue incrementing what appears to be long distances in distance metrics.
• Solutions include a method called "poisioned reverse" and will address the slow updates by assigning infinite loops to various hops and distance metrics.

Heirachical Routing

• Network is a collection of interconnected routers.
• One router was indistinguishable from another in the sense that all routers executed the same routing algorithm to compute routing paths through the entire network.
• Scale: As the number of routers becomes large, the overhead involved in computing, storing, and communicating routing information becomes prohibitive.
• Administrative Autonomous - ideally, an organization should be able to run and administer its network as it wishes, while still being able to connect its network to other outside networks.
• These problems can be solved by organizing routers into autonomous systems (AS), with each AS consisting of a group of routers that are typically under the same administrative control.

Additional Routing Topics

• Routers also run the same routing algorithm (for example, an LS or DV algorithm) and have information about each other.
• AS routing protocol are the running computations within an autonomous system.
• Intra and inter autonomous system routing configurations will perform tasks such as: obtaining reachability information from neighbouring ASs and propagating the reachability information to all routers internally.
• Inter protocol tasks occur when router receives a datagram and it should forward packets to gateway routers.
• Common Inter-AS routing options:
  • RIP: Routing Information Protocol
  • OSPF: Open Shortest Path First
  • IGRP: Interior Gateway Routing Protocol