What does the network layer do on the sending side and on the receiving side?
Sending side: encapsulates segments into datagrams. Receiving side: delivers segments to the transport layer. Network layer protocols run in every host and router.
Forwarding vs routing, with the trip analogy.
Forwarding: move packets from router's input to appropriate router output (getting through a single interchange). Routing: determine route taken by packets from source to dest (planning the trip).
How do the routing algorithm and the forwarding table relate?
The routing algorithm determines the end-end path through the network; the forwarding table determines local forwarding at this router (header value → output link).
What is "connection setup" at the network layer, and in which architectures?
A 3rd function in some architectures (ATM, frame relay, X.25): before datagrams flow, the two end hosts and intervening routers establish a virtual connection — routers get involved.
Example network service-model guarantees for individual datagrams and for a flow.
Individual datagrams: guaranteed delivery; guaranteed delivery with less than 40 msec delay. Flow: in-order datagram delivery; guaranteed minimum bandwidth; restrictions on changes in inter-packet spacing.
Datagram network vs VC network service, and how they differ from TCP/UDP services.
Datagram: network-layer connectionless service; VC: network-layer connection service. Unlike transport: service is host-to-host, there is no choice (network provides one or the other), and it is implemented in the network core.
Internet (datagram) vs ATM (VC): where is the complexity, and why?
Internet: "smart" end systems (computers) that can adapt and recover — simple inside network, complexity at "edge". ATM: evolved from telephony with "dumb" end systems (telephones) and strict timing needs — complexity inside network.
Two key router functions, and which plane does each belong to?
Run routing algorithms/protocols (RIP, OSPF, BGP) — routing, management control plane (software). Forward datagrams from incoming to outgoing link — forwarding data plane (hardware: input ports, high-speed switching fabric, output ports).
The three parts of the Internet network layer.
Routing protocols (path selection: RIP, OSPF, BGP) → forwarding table; IP protocol (addressing conventions, datagram format, packet handling conventions); ICMP protocol (error reporting, router "signaling").
IP header: what do "time to live" and "upper layer" mean?
Time to live: max number remaining hops (decremented at each router). Upper layer: upper layer protocol to deliver payload to.
Which IP header fields are used for fragmentation/reassembly? What is the overhead of TCP over IP?
16-bit identifier, flgs, fragment offset. Overhead: 20 bytes of TCP + 20 bytes of IP = 40 bytes + app layer overhead.
What is MTU, and where are fragments reassembled?
MTU (max. transfer size): the largest possible link-level frame; different link types have different MTUs. Fragments are reassembled only at the final destination.
4000-byte datagram, MTU 1500. Give each fragment's length, flag and offset.
(1500, fragflag 1, offset 0), (1500, fragflag 1, offset 185), (1040, fragflag 0, offset 370); same ID x. Data: 3980 = 1480 + 1480 + 1020.
How is the fragment offset computed?
Offset = position (in bytes) of the fragment's first data byte ÷ 8. E.g., 1480/8 = 185; 2960/8 = 370.
What is an IP address, and what is an interface?
IP address: 32-bit identifier for host, router interface. Interface: connection between host/router and physical link. IP addresses are associated with each interface (routers typically have multiple).
Subnet part vs host part; definition of a subnet.
Subnet part: high order bits; host part: low order bits. Subnet: device interfaces with the same subnet part of IP address, which can physically reach each other without intervening router.
Recipe for finding the subnets in a network.
Detach each interface from its host or router, creating islands of isolated networks; each isolated network is called a subnet.
What does CIDR stand for, and what does x mean in a.b.c.d/x?
Classless InterDomain Routing: subnet portion of arbitrary length; x is the # bits in the subnet portion of the address (e.g., 200.23.16.0/23).
Two ways for a host to get an IP address; DHCP's goal.
Hard-coded by system admin in a file, or DHCP ("plug-and-play"). DHCP goal: allow a host to dynamically obtain its IP address from a network server when it joins the network (lease renewal, address reuse, support for mobile users).
The four DHCP messages, in order.
DHCP discover (host broadcasts) [optional] → DHCP offer (server) [optional] → DHCP request (host) → DHCP ack (server).
What can DHCP return besides the IP address?
Address of first-hop router for client; name and IP address of DNS server; network mask (network vs host portion of the address).
How is a DHCP request carried on the LAN?
Encapsulated in UDP, in IP, in 802.1 Ethernet; the Ethernet frame is broadcast (dest: FFFFFFFFFFFF) and received at the router running the DHCP server.
How does an organization get its subnet part, and what is route aggregation?
It gets an allocated portion of its provider ISP's address space. Route aggregation: hierarchical addressing lets the ISP advertise one prefix (e.g., "Send me anything with addresses beginning 200.23.16.0/20").
What happens to routing when Organization 1 moves to ISPs-R-Us?
ISPs-R-Us advertises a more specific route: "199.31.0.0/16 or 200.23.18.0/23".
What is ICANN and what does it do?
Internet Corporation for Assigned Names and Numbers: allocates addresses, manages DNS, assigns domain names, resolves disputes.
What does NAT make the outside world see?
All datagrams leaving the local network have the same single source NAT IP address with different source ports.
What are the benefits of NAT?
One address from ISP; change internal addresses or ISP without notifying the outside; inside devices not explicitly addressable from outside (a security plus).
Three things a NAT router must do.
Outgoing: replace (source IP, port #) with (NAT IP, new port #). Remember every translation pair in the NAT translation table. Incoming: replace (NAT IP, new port #) in dest fields with the stored (source IP, port #).
How many simultaneous connections can NAT support with one LAN-side address, and why is NAT controversial?
16-bit port-number field: 60,000 simultaneous connections. Controversial: routers should only process up to layer 3; violates end-to-end argument (apps such as P2P must account for NAT); address shortage should instead be solved by IPv6.
What is ICMP used for?
Used by hosts & routers to communicate network-level info: error reporting (unreachable host, network, port, protocol) and echo request/reply (ping).
How is an ICMP message carried, and what does it contain?
ICMP msgs are carried in IP datagrams; message = type, code + first 8 bytes of the IP datagram causing the error.
ICMP type/code for echo request, echo reply, TTL expired, and dest port unreachable.
Echo request (ping): 8/0. Echo reply (ping): 0/0. TTL expired: 11/0. Dest port unreachable: 3/3.
How does traceroute discover the routers on a path, and when does it stop?
It sends UDP segments with TTL = 1, 2, 3, …; the nth router discards the nth set and returns ICMP type 11, code 0 (with its name and IP address); the source records RTTs. It stops when the destination returns ICMP "port unreachable" (type 3, code 3).
IPv6: address size, and the purpose of priority, flow label and next header.
128-bit source and destination addresses. Priority: priority among datagrams in flow. Flow label: identify datagrams in the same "flow". Next header: identify upper layer protocol for data.
Three changes in IPv6 besides the address size.
Checksum removed entirely (to reduce processing time at each hop); options allowed but outside the header, indicated by "Next Header"; ICMPv6 with additional message types (e.g., "Packet Too Big") and multicast group management.
What is tunneling in the IPv4-to-IPv6 transition, and why is it needed?
An IPv6 datagram is carried as payload in an IPv4 datagram among IPv4 routers — needed because not all routers can be upgraded simultaneously (no "flag days").
What is the cost of a path, and what does a routing algorithm find?
Cost of path = sum of its link costs: c(x1,x2) + c(x2,x3) + … + c(xp−1,xp). A routing algorithm finds the least cost path. (Link cost could always be 1, or inversely related to bandwidth or to congestion.)
Global vs decentralized routing algorithms.
Global: all routers have complete topology and link cost info ("link state"). Decentralized: router knows neighbors and link costs to them; iterative computation and exchange with neighbors ("distance vector").
Static vs dynamic routing algorithms.
Static: routes change slowly; dynamic: routes change more quickly (periodic update, in response to link cost changes).
What does Dijkstra's algorithm assume and compute?
Net topology and link costs are known to all nodes (via "link state broadcast"). It computes least cost paths from one node (the source) to all other nodes, giving that node's forwarding table. After k iterations, least cost paths to k destinations are known.
Dijkstra notation: c(x,y), D(v), p(v), N'.
c(x,y): link cost from x to y (∞ if not direct neighbors). D(v): current cost of path from source to v. p(v): predecessor node along the path to v. N': set of nodes whose least cost path is definitively known.
Dijkstra's update rule.
For all v adjacent to w and not in N': D(v) = min( D(v), D(w) + c(w,v) ) — new cost to v is either the old cost or the shortest path cost to w plus the cost from w to v.
Complexity of Dijkstra's algorithm, and what problem can occur?
n(n+1)/2 comparisons: O(n²) (more efficient implementations possible: O(n log n)). Oscillations are possible, e.g., when link cost equals the amount of carried traffic.
Write the Bellman-Ford equation and say how the next hop is chosen.
dx(y) = min over all neighbors v of { c(x,v) + dv(y) }. The node achieving the minimum is the next hop on the shortest path, used in the forwarding table.
Distance vector: when does a node send its DV?
From time to time, and whenever its DV changes.
Why is the distance vector algorithm "iterative, asynchronous" and "distributed"?
Iterative, asynchronous: each local iteration is caused by a local link cost change or a DV message from a neighbor. Distributed: each node notifies neighbors only when its DV changes; they notify theirs if necessary.
LS vs DV: message complexity.
LS O(nE); DV only between neighbors.
LS vs DV: speed of convergence.
LS O(n²), may oscillate; DV varies, may have routing loops and the count-to-infinity problem.
LS vs DV: robustness.
LS nodes advertise only link costs and compute their own tables; in DV a wrong path cost spreads because each node's table is used by others.
Why is routing hierarchical, and what is an autonomous system?
Scale (600 million destinations; table exchange would swamp links) and administrative autonomy. An AS is a region of aggregated routers that run the same intra-AS routing protocol; a gateway router sits at its edge with a link to another AS.
The two inter-AS routing tasks of AS1.
1. Learn which destinations are reachable through AS2 and which through AS3. 2. Propagate this reachability info to all routers in AS1.
What is hot potato routing?
Send the packet towards the closest of the gateways: use intra-AS routing info to find the least-cost path to each gateway, choose the gateway with the smallest least cost, and enter (x, I) for the interface leading to it.
RIP: algorithm, metric, max hops, update period, advertisement size.
Distance vector; metric = # hops, each link cost 1; max = 15 hops; DVs exchanged with neighbors every 30 sec (advertisement); up to 25 destination subnets per advertisement.
RIP: router D reaches z in 7 hops via B. Neighbor A advertises z at 4 hops. How does D update its entry for z?
A advertises z at 4 hops; via A, D reaches z in 4 + 1 = 5 hops, fewer than its current 7 via B, so D changes its entry for z to next router A, 5 hops.
Which process manages RIP tables, and how are advertisements sent?
An application-level process called route-d (daemon); advertisements are sent in UDP packets, periodically repeated.
OSPF: algorithm, how advertisements spread, and how they are carried.
Link state algorithm with Dijkstra's route computation; each advertisement carries one entry per neighbor and is flooded to the entire AS; carried in OSPF messages directly over IP (not TCP or UDP). IS-IS is nearly identical.
OSPF "advanced" features not in RIP.
Security (all OSPF messages authenticated); multiple same-cost paths allowed (only one in RIP); multiple cost metrics per link for different TOS; integrated uni- and multicast support (MOSPF).
What is BGP, and what do eBGP and iBGP do?
Border Gateway Protocol: the de facto inter-domain routing protocol ("glue that holds the Internet together"). eBGP: obtain subnet reachability info from neighboring ASs. iBGP: propagate reachability info to all AS-internal routers. Routes are chosen by reachability info and policy.
Why are intra-AS and inter-AS routing different? (policy, scale, performance)
Policy: inter-AS admins want control over how traffic is routed and who routes through their net; intra-AS has a single admin, so no policy decisions. Scale: hierarchical routing saves table size and update traffic. Performance: intra-AS can focus on performance; inter-AS policy may dominate.