Network Layerطبقة الشبكة

• Transports segment from sending to receiving host: on sending side encapsulates segments into datagrams; on receiving side delivers segments to transport layer.
• Network layer protocols in every host, router; router examines header fields in all IP datagrams passing through it.

Analogous to TCP/UDP services, but:

• Service: host-to-host
• No choice: network provides one or the other
• Implementation: in network core

The Internet network layer (slide 14)

• Routing protocols: path selection — RIP, OSPF, BGP → forwarding table
• IP protocol: addressing conventions, datagram format, packet handling conventions
• ICMP protocol: error reporting, router "signaling"

• Routers typically have multiple interfaces.
• A host typically has one or two interfaces (e.g., wired Ethernet, wireless 802.11).
• Example: 223.1.1.1 = 11011111 00000001 00000001 00000001.
• Wired Ethernet interfaces are connected by Ethernet switches; wireless WiFi interfaces by a WiFi base station.

DHCP goal

• Allow host to dynamically obtain its IP address from network server when it joins network
• Can renew its lease on address in use
• Allows reuse of addresses (only hold address while connected/"on")
• Support for mobile users who want to join network

DHCP client-server scenario (slide 30)

• Three subnets joined by one router — 223.1.1.0/24 (hosts 223.1.1.1–.3, router interface 223.1.1.4), 223.1.2.0/24 (hosts 223.1.2.1, 223.1.2.2, router 223.1.2.9, the DHCP server) and 223.1.3.0/24 (hosts 223.1.3.1, 223.1.3.2, router 223.1.3.27). An arriving DHCP client needs an address in this network (223.1.2.0/24).

DHCP can return more than the allocated IP address

• Address of first-hop router for client
• Name and IP address of DNS server
• Network mask (indicating network versus host portion of address)

Motivation: one IP address as far as the outside world is concerned

• Range of addresses not needed from ISP: just one IP address for all devices
• Can change addresses of devices in local network without notifying outside world
• Can change ISP without changing addresses of devices in local network
• Devices inside local net not explicitly addressable, visible by outside world (a security plus)

• 16-bit port-number field: 60,000 simultaneous connections with a single LAN-side address!

NAT is controversial

• Routers should only process up to layer 3
• Violates end-to-end argument — NAT possibility must be taken into account by app designers, e.g., P2P applications
• Address shortage should instead be solved by IPv6

• Network-layer "above" IP: ICMP msgs carried in IP datagrams.
• ICMP message: type, code plus first 8 bytes of IP datagram causing error.

Other changes from IPv4

• Checksum: removed entirely to reduce processing time at each hop
• Options: allowed, but outside of header, indicated by "Next Header" field
• ICMPv6: new version of ICMP — additional message types, e.g. "Packet Too Big"; multicast group management functions

• Not all routers can be upgraded simultaneously — no "flag days".
• How will the network operate with mixed IPv4 and IPv6 routers?

Graph: G = (N,E)

• N = set of routers = { u, v, w, x, y, z }
• E = set of links = { (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }
• c(x,x') = cost of link (x,x'), e.g., c(w,z) = 5; cost could always be 1, or inversely related to bandwidth, or to congestion
• Cost of path (x1, …, xp) = c(x1,x2) + c(x2,x3) + … + c(xp−1,xp)

• Net topology, link costs known to all nodes — via "link state broadcast"; all nodes have same info.
• Computes least cost paths from one node ("source") to all other nodes — gives forwarding table for that node.
• Iterative: after k iterations, know least cost path to k dest.'s.

• Update rule on slide 60: D(v) = min( D(v), D(w) + c(w,v) ); e.g. D(z) = min( D(z), D(y) + c(y,z) ) = min(14, (10+2)) = 12.
• The resulting least-cost paths (red on slide 60): u→x, u→w, w→v, v→y, y→z.

Resulting forwarding table in u (slide 62)

• v → link (u,v)
• x, y, w, z → link (u,x)

Discussion (slide 63)

• n nodes: each iteration checks all nodes not in N; n(n+1)/2 comparisons: O(n²); more efficient implementations possible: O(n log n).
• Oscillations possible, e.g., if link cost equals amount of carried traffic.

Distance vector algorithm

• From time-to-time, each node sends its own distance vector estimate to neighbors.
• When x receives a new DV from a neighbor, it updates its own DV using B-F: Dx(y) ← min_v{c(x,v) + Dv(y)}.
• Iterative, asynchronous: each local iteration is caused by a local link cost change or a DV update message from a neighbor.
• Distributed: each node notifies neighbors only when its DV changes; neighbors then notify their neighbors if necessary.

• Dx(y) = min{ c(x,y) + Dy(y), c(x,z) + Dz(y) } = min{2+0, 7+1} = 2.
• Dx(z) = min{ c(x,y) + Dy(z), c(x,z) + Dz(z) } = min{2+1, 7+0} = 3.

• Forwarding table configured by both intra- and inter-AS routing: intra-AS sets entries for internal dests; inter-AS & intra-AS set entries for external dests.

Intra-AS routing = interior gateway protocols (IGP)

• RIP: Routing Information Protocol
• OSPF: Open Shortest Path First
• IGRP: Interior Gateway Routing Protocol (Cisco proprietary)

A-to-D advertisement (slide 85)

• w: next -, 1 hop
• x: next -, 1 hop
• z: next C, 4 hops

• "Open": publicly available.
• Uses link state algorithm: LS packet dissemination; topology map at each node; route computation using Dijkstra's algorithm.
• OSPF advertisement carries one entry per neighbor; advertisements flooded to entire AS.
• Carried in OSPF messages directly over IP (rather than TCP or UDP).
• IS-IS routing protocol: nearly identical to OSPF.

• BGP allows a subnet to advertise its existence to rest of Internet: "I am here".