计算机网络

Chapter 4 - The Network Layer: Data Plane

2019-12-01 04:00 CST
2019-12-12 00:45 CST
CC BY-NC 4.0

4.1 Overview of Network Layer

4.1.1 Forwarding and Routing: The Data and Control Planes

Primary role of the network layer: to move packets from a sending host to a receiving host.

Two important network-layer functions to move packets:

  • Forwarding (switching): when a packet arrives at a router’s input link, the router must move the packet to the appropriate output link. A packet might also be blocked from exiting a router, or might be duplicated and sent over multiple outgoing links.
  • Routing: determine the route or path taken by packets as they flow from a sender to a receiver using routing algorithms.

Forwarding refers to the router-local action of transferring a packet from input link to output link, takes place at very short timescales, thus is typically implemented in hardware.

Routing refers to the network-wide process that determines the end-to-end paths that packets take, takes place on much longer timescales and often implemented in software.

Forwarding table: a router forwards a packet by examining the value of one or more fields in the arriving packet’s header, then using these header values to index into its forwarding table. The value in the forwarding table entry for thoes values indicates the outgoing link interface at that router to which the packet is to be forwarded.

Control Plane: The Traditional Approach

Traditional Approach

A routing algorithm runs in each and every router and both forwarding and routing function are contained within a router. The algorithm communicates with the routing algorithm in other routers to compute the values of its forwarding table.

The forwarding and routing functions can be configured directly by human network operators, and no routing protocols would be required.

Control Plane: The SDN Approach

SDN Approach

A physically separate (from the routers) remove controller computes and distributes the forwarding tables to be used by each and every router. The routing device performs forwarding only while the remote controller computes and distributes forwarding tables.

This control-plane approach is at the heart of software-defined networking (SDN), where network is software-defined because the controller that computes the tables and interacts with routers is implemented in software.

4.1.2 Network Service Model

The network service model defines the characteristics of end-to-end delivery of packets between sending and receiving hosts.

  • Guaranteed delivery: guarantees that a packets sent by a source host will eventually arrive at the destination host.
  • Guaranteed delivery with bounded delay: delivery within a host-to-host delay bound.
  • In-order packet delivery: packets arrive in the order they were sent.
  • Guaranteed minimal bandwidth: as long as the sending host transmits bits at a rate below the limit, all packets are eventually delivered to the destination host.
  • Security: encrypt all datagrams at the source and decrypt them at the destination.
  • Et cetera.

The Internet’s network layer provides a single service, known as best-effort service. Packets are neither guaranteed to be received in order nor is their eventual delivery even guaranteed. There is no guarantee on delay not there is a minimal bandwidth guarantee. (best-effort service = no service at all)

4.2 What’s Inside a Router?

Router Architecture

  • Input ports
    • Performs the physical layer function of terminating an incoming physical link at a router.
    • Performs link-layer functions needed to interoperate with the link layer at the other side of the incoming link.
    • Most crucially, a lookup function is also performed at the input port. Here the forwarding table is consulted to determine the router output to which the packet should be forwarded via the switching fabric. Control packets are forwarded from input port to the routing processor.
  • Switching fabric: connects the router’s input ports to its output ports.
  • Output ports: stores packets received from the switching fabric and transmits these packets on the outgoing link by performing the necessary link-layer and physical-layer functions.
  • Routing processor: performs control-plane functions.
    • In traditional routers, it executes the routing protocols, maintains routing tables and attached link state information, and computes the forwarding table for the router.
    • In SDN routers, the routing processor is responsible for communicating with the remote controller in order to receive forwarding table entries and install these entries in input ports.

Input ports, output ports and switching fabric are almost always implemented in hardware. The control plane functions are usually implemented in software and execute on the routing processor.

4.2.1 Input Port Processing and Destination-Based Forwarding

Input Processing

The router matches a prefix of the packet’s destination address with the entries in the table. When there are multiple matches, the router uses the longest prefix matching rule.

Once the output port has been determined, the packet can be sent into the switching fabric. In some designs, a packet may be temporarily blocked from entering the switching fabric if packets from other input ports are currently using the fabric. A blocked packet will be queued at the input port and then scheduled to cross the fabric at a later point.

Other important actions:

  • physical and link-layer processing
  • version number, checksum and time-to-live field must be checked and the latter two fields rewritten
  • counters used for network management must be updated

4.2.2 Switching

Via Memory

Switching via memory: simplest, earliest method, where input and output ports functioned as traditional I/O devices in a traditional operating system. If memory bandwidth allows a maximum of $B$ packets per second to be written into or read from memory, then the overall forwarding throughput must be less then $B/2$. Two packets cannot be forwarded at the same time.

Via Bus

Switching via a bus: an input port transfers a packet directly to the output port over a shared bus, without intervention by the routing processor. This is typically done by having the input port pre-pend a switch a switch-internal label (header) to the packet indicating the local output port. All output port receive the packet, but only the port that matches the label will keep the packet. The label is then removed at the output port. Only one packet can cross the bus at a time.

Via CrossBar

Switching via an interconnection network: A crossbar switch is an interconnection network consisting of $2N$ buses that connect $N$ input ports to $N$ output ports. Crossbar switches are capable of forwardning multiple packets in parallel, which is non-blocking (not blocked as long as no other packet is being forwarded to the same output port).

4.2.3 Output Port Processing

Output Processing

Output port takes packets from output port’s memory and transmits them over the output link. This includes selecting and de-queueing packets for transmission, and performing the needed link-layer and physical-layer transmission functions.

4.2.4 Where Does Queuing Occur?

Suppose input and output line speeds (transmission rates) all have an identical transmission rate of $R_{\text{line}}$ packets per seconds, and there are $N$ input ports and $N$ output ports.

All packets have the same fixed length and arrive to input ports in a synchronous manner (the time to send a packet on any link is equal to the time to receive a packet on any link, during this interval, either zero or one packets can arrive on an input link).

Define $R_{\text{switch}}$ as the rate at which packets can be moved from input port to output port. If $R_{\text{switch}}$ is $N$ times faster than $R_{\text{line}}$, then only negligible queueing will occur at the input ports. (In the worst case $N$ input lines are receiving packets and all packets are to be forwarded to the same output port, each batch of $N$ packets can be cleared before the next batch arrives.)

Input Queueing

If switch fabric is not fast enough, packet queuing can also occur at the input ports as packets must join input port queues to wait their turn to cross the fabric.

HOL

Head-of-the-line (HOL) blocking is a queued packet in an input queue must wait for transfer through the fabric (even though its output port is free) because it is blocked by another packet at the head of the line.

Output Queueing

Output Queueing

When the output port cannot transmit all packets, the rest packets must be queued. The number of queued packets can grow large enough to exhaust available memory at the output port.

When there is no enough memory to buffer, a decision must be made to either drop the arriving packet (drop-tail) or remove one or more already-ququed packets to make room for new packet.

4.2.5 Packet Scheduling

First-In-First-Out (FIFO)

FIFO

Also known as first-come-first served (FCFS), the output port delects packets for link transmission in the same order in which they arrived at the output link queue.

Priority Queueing

PQ

The priority queuing discipline will transmit a packet from the highest priority class that has a nonempty queue. The choice among packets in the same priority class is typically done in a FIFO manner.

Round Robin and Weighted Fair Queueing (WFQ)

RR

A round robin scheduler alternates service among priority classes. The work-conserving queuing discipline will never allow the link to remain idle whenever there are packets queued. A work-conversing round robin discipline looks for a packet of a given class but finds none will immediately check the next class in the round robin sequence.

WFQ differs from RR that each class may receive a differential amount of service in any interval of time. (partition of service equals to $w_i/\sum w_j$ where $w_i$ is the weight of class $i$.)

4.3 The Internet Protocol (IP)

4.3.1 IPv4 Datagram Format

IPv4

  • Version number: IP protocol version of datagram.
  • Header length: determine where in the IP datagram the payload actually begins (typical IP datagram has a 20-byte header).
  • Type of service (TOS): allow different types of IP datagrams to be distinguished from each other.
  • Datagram length: total length of IP datagram (header plus data), measured in bytes.
  • Identifier, flags, fragmentation offset: related to fragmentation (IPv6 does not allow for fragmentation)
  • Time-to-live (TTL): ensure that datagrams do not circulate forever in the network. This field is decremented by one each time the datagram is processed by a router. If TTL reaches 0, a router must drop that datagram.
  • Protocol: used only when an datagram reaches its final destination. (6=TCP, 17=UDP) The protocol number is the glue that binds the network and transport layers together, whereas the port number is the glue that binds the transport and application layers together.
  • Header checksum
  • Source and destination IP addresses
  • Options
  • Data (payload)

4.3.2 IPv4 Datagram Fragmentation

The maximum amout of data that a link-layer frame can carry is called the maximum transmission unit (MTU).

Because each IP datagram is encapsulated within the link-layer frame for transport from one router to the next router, the MTU of the link-layer protocol places a hard limit on the length of an IP datagram.

Fragmentation

When a destination host receives a series of datagrams from the same source, it needs to determine whether any of these datagrams are fragments of some original, larger datagram. If some datagram are fragments, it must further determine when it has received the last fragment and how the fragments should be pieced back together. IPv4 put identification, flag and fragmentation offsets in the IP datagram header.

The sending host increments the identification number for each datagram it sends. When a router needs to fragment a datagram, each resulting fragment is stamped with the source address, destination address and identification number of the origin datagram. The last fragment has a flag bit set to 0, whereas all other fragments have this bit set to 1 (has more fragments). The offset field is used to specify where the fragments fits within the original IP datagram.

4.3.3 IPv4 Addressing

An IP address is technically associated with an interface, rather than with the host or router containing that interface.

Each IP address is 32 bits long (4 bytes), are written in so-called dotted-decimal notation. Each interface on every host and router in the global Internet must have an IP address that is globally unique (except behind NATs).

Subnet

Interfaces interconnected to each other by a network that contains no routers (Ethernet switch or wireless access point) along with one router interface forms a subnet. For example, the upper-left subnet shares an address 223.1.1.0/24, where the /24 notation (subnet mask) indicates that the leftmost 24 btis define the subnet address. The 223.1.1.0/24 subnet consists of the three host interfaces and one router interface.

To determine the subnets, detach each interface from its host or router, creating islands of isolated networks, with interface terminating the end points of the isolated networks. Each of these isolated networks is called a subnet.

The Internet’s address assignment strategy is known as Classless Interdomain Routing (CIDR), the 32-bit address is divided into two parts and has the form a.b.c.d/x, where $x$ indicates the number of bits in the first part of the address.

The $x$ most significant bits of an address constitude the network portion of the IP address (referred to as prefix of the address). IP addresses of devices within the organization will share the common prefix. The remaining $32-x$ bits can be thought of as distinguishing among devices within the organization, all of which have the same prefix.

Before CIDR was adopted, the network portions of an IP address were constrained to be 8, 16, or 24 bits in length, an addressing scheme known as classful addressing. Subnets with 8, 16, and 24-bit subnet addresses were known as class A, B, and C networks respectively.

The IP broadcast address is 255.255.255.255. When a host sends a datagram with destination address 255.255.255.255, the message is delivered to all hsots on the same subnet.

Obtaining a Block of Addresses

A network administrator first contact its ISP, ISP divide its address block and give one of these blocks to organizations.

The Dynamic Host Configuration Protocol

DHCP allows a host to obtain an IP address automatically. A given host receives the same IP address each time it connects to the network, or a host may be assigned a temporaty IP address that will be different each time the host connects to the network.

DHCP is referred to as a plug-and-play or zeroconf protocol.

DHCP

  • DHCP server discovery: a newly arriving host finds a DHCP server using a DHCP discover message, which sends (broadcasts) within a UDP packet to port 67.
  • DHCP server offer: A DHCP server receiving a DHCP discover message responds to the client with a DHCP offer message that is broadcast to all nodes on the subnet, containing the transaction ID, the proposed IP address, network mask and an IP address lease time (the amount of time for which the IP address will be valid).
  • DHCP request: the newly arriving client will choose from one or more offers and respond to its selected offer with a DHCP request message, echoing back the configuration parameters.
  • DHCP ACK: the server responds with a DHCP ACK message confirming the requested parameters.

4.3.4 Network Address Translation (NAT)

NAT

The NAT router behaves to the outside world as a single device with a single IP address.

When NAT router receives a datagram, it generates a new source port number for the datagram and replace the IP address and port number in it. When generating a new source port number, the NAT router can select any source port number that is not currently in the NAT translation table.

When NAT router receives a response, it indexes the NAT translation table using the destination IP address and port number to obtain the appropriate IP address and port in the NAT network, and rewrite the destination into the datagram.

4.3.5 IPv6

IPv6 Datagram Format

  • Expanded addressing capabilites: 128 bits of IP address, and introduced a new type of address called anycast address that allows a datagram to be delivered to any one of a group of hosts.
  • A streamlined 40-byte header: a fixed-length header allows for faster processing by a router.
  • Flow labeling: IPv6 has an elusive definition of a flow, allows labeling of packets belonging to particular flows for which the sender requests special handling.

IPv6 Datagram

  • Version: value 6.
  • Traffic class: 8 bits, like TOS in IPv4.
  • Flow label: 20 bits, identify a flow of datagrams.
  • Payload length: 16 bits, giving the number of bytes of payload.
  • Next header: identifies the protocol to which the contents in this datagram will delivered (TCP/UDP/etc.) like protocol field in IPv4.
  • Hop limit: TTL.
  • Source and destination address
  • Data

Several fields in IPv4 are no longer present in IPv6 datagram:

  • Fragmentation: IPv6 does not allow fragmentation. If an IPv6 datagram is too big, then the router drops the datagram and sends a “Packet Too Big” ICMP error message back to the sender.
  • Header checksum: the checksum is redundant.
  • Options: options can be pointed to by next header field in IPv6.

Transitioning from IPv4 to IPv6

Tunneling:

Tunneling

4.4 Generalized Forwarding and SDN

Generalized Forwarding

Packet switch contains a match-plus-action table (flow table) that is computed and distributed by a remote controller:

  • a set of header field values
  • a set of counters
  • a set of actions to be taken:
    • forwarding
    • dropping
    • modify-field