Networking Concepts Quiz

Introduction to Computer Networking

• Chapter 4, Network Layer, 6th edition by Kurose and Ross, Addison-Wesley, March 2012
• Note on use of slides: slides freely available for all users; Users are permitted to adapt and modify the slides but must cite the source and copyright of the slides.

Chapter 4: Network Layer

• Chapter goals: understand principles behind network layer services, including network layer service models, forwarding and routing, how routers work, routing (path selection), broadcast, multicast, instantiation, and implementation in the Internet.
• 4.1 Introduction
• 4.2 Virtual Circuit and Datagram Networks
• 4.3 What's inside a router
• 4.4 IP: Internet Protocol
  • Datagram format
  • IPv4 addressing
  • ICMP
  • IPv6
• 4.5 Routing Algorithms
  • Link state
  • Distance vector
  • Hierarchical routing
• 4.6 Routing in the Internet
  • RIP
  • OSPF
  • BGP
• 4.7 Broadcast and Multicast Routing

Network Layer Functions

• Forwarding: moves packets from a router's input to the appropriate router output
• Routing: determines the route taken by packets from source to destination
• Routing Algorithms
• Interplay between Routing and Forwarding: Routing algorithm determines the end-to-end path through the network, while the forwarding table determines local forwarding at the router
• Connection Setup: 3rd important function in some network architectures (ATM, frame relay, X.25) involves routers establishing virtual connections before datagrams flow.
• Network vs. Transport Layer Connection Service:
  • Network layer: between two hosts (may involve intervening routers in the case of virtual circuits)
  • Transport Layer: between two processes
• Network Service Model:
  • Example services for individual datagrams: guaranteed delivery, guaranteed delivery with less than 40 msec delay
  • Example services for a flow of datagrams: in-order datagram delivery, guaranteed minimum bandwidth, restrictions on changes in inter-packet spacing
• Virtual Circuits:
  • Behavior similar to a telephone circuit
  • Call setup and teardown for each call
  • Each packet carries a VC identifier (instead of destination address)
  • Routers maintain "state" for each passing connection
  • Dedicated resources are allocated to the VC for predictable service
• Virtual Circuit Implementation:
  • Path from source to destination
  • VC numbers (one for each link along path)
  • Entries in forwarding tables in routers along the path
• Datagram Networks:
  • No call setup at network layer
  • No network-level concept of a connection
  • Packets are forwarded using the destination host address
• Datagram Forwarding Table:
  • To deal with the sheer number of IP addresses, use ranges rather than listing each individual IP.
• Longest Prefix Matching:
  • Using IP destination address to find best matching in local forwarding table (longest prefix matching)
• Datagram or VC Network: Why?
  • Internet (datagram): data exchange, elastic service, many link types
  • ATM (VC): evolved from telephony, strict timing, reliability, need for guaranteed service, dumb end systems
• Router Architecture Overview:
  • two main functions: execute routing algorithms and forward datagrams from incoming to outgoing links
  • Has a routing processing and forwarding data plane
• Input Port Functions:
  • Decentralized switching
  • Goal: complete input port processing at “line speed”
  • Queuing: for when datagrams arrive faster than forwarding rate into fabric
• Switching Fabrics: memory, bus, crossbar
• Three types: memory, bus, crossbar
• Switching via Memory
• Switching via a Bus
• Switching via Interconnection Network
• Output Ports:
  • Buffering required from fabric's speed to the output line.
  • Scheduling datagrams
• Input Port Queuing
• How much buffering? (RFC 3439) for links with typical RTT.
• Interplay between routing and forwarding
• Graph abstraction: utility for network contexts (e.g., P2P)
• Graph Abstraction: costs of link(x,x')
• Routing Algorithm Classification:
  • Global vs. Decentralized:
    • Global: all routers have complete topology, link cost info
    • Decentralized: routers know physically connected neighbors, link costs to neighbors. Iterative process exchanging information with neighbors.
  • Static vs. Dynamic:
    • Static: routes change slowly over time
    • Dynamic: routes change more quickly, have periodic updates, and in response to link cost changes
• Dijkstra's Algorithm:
  • Notation: introducing variables for link cost, current value of cost, predecessor node.
  • Initialization: steps for initializing the algorithm
  • Loop: steps for iteratively finding shortest paths
• Dijkstra's Algorithm: example with resulting shortest-path tree from u and forwarding table.
• Dijkstra's Algorithm, discussion:
• Distance Vector Algorithm
  • Bellman-Ford equation (dynamic programming)
  • Introducing cost of path from x-to-y
  • The node achieving minimum is the next hop used in forwarding table
• Distance Vector Algorithm:
  • defining Dx(y) = estimate of least cost from x-to-y .
• Distance Vector Algorithm: key idea
• Distance vector algorithm, iterative, asynchronous with each node
• Distance vector algorithm, distributed
• Distance vector algorithm, link cost changes
• Inter-AS routing protocols, and BGP
• BGP: Border Gateway Protocol, the de facto inter-domain routing protocol, glue that holds the Internet together
• BGP protocols
  • eBGP: to get subnet from neighboring ASs
  • iBGP: propagate info to all AS-internal routers
• BGP route selection
• Router may learn about more than one route to a destination AS; selects route based on 4 criteria: local preference attribute, shortest AS path, closest NEXT-HOP router, and other criteria.
• BGP messages
• Putting it Altogether: How Does an Entry Get Into a Router's Forwarding Table?
• How does entry get in forwarding table?
• Router identifies port for route
• Hot Potato Routing
• BGP Routing policy
• Why different intra and Inter-AS routing?

Test your understanding of the network layer and routing protocols in this quiz. Explore important concepts such as encapsulation, BGP messages, and route selection. Perfect for students studying computer networking.