Network layer: control plane


Last class a router looked up a destination address in its forwarding table and moved the packet accordingly. Today answers the question that leaves open: where does that table come from? Two quite different protocols are needed, because the problem splits in two. Inside one organization, routers can share complete information and compute genuinely shortest paths, which is what Open Shortest Path First (OSPF) does, using a graph algorithm you already know. Between organizations, nobody will share complete information and nobody wants shortest paths anyway; each organization wants the paths that serve its business interests. That job belongs to the Border Gateway Protocol (BGP), which is less an algorithm than a negotiation. We also pick up one loose end from last class, IPv6, the successor to version 4 of the Internet Protocol (IP), and close with the alternative to both protocols: a single controller that computes every table from one place.

Slides from class

Files:

Additional information:

Agenda

These notes begin with IPv6, which we did not reach last class, and then cover routing algorithms in the abstract, OSPF for routing within an autonomous system, BGP for routing between autonomous systems, and the software-defined networking (SDN) approach to the control plane. The data plane from last class is unchanged throughout; only the source of the forwarding table differs.

Notes

We finish the IP header story first, then turn to the question of where forwarding tables originate.

IPv6: a loose end from last class

The initial motivation for IPv6 was simple: the 32-bit IPv4 address space has been completely allocated. Three additional motivations shaped the design. Speed of processing and forwarding, through a fixed 40-byte header. Enabling different network-layer treatment of flows. And learning the lessons of IPv4 generally.

The IPv6 header carries a version field, a priority field identifying priority among datagrams in a flow, a flow label identifying datagrams in the same flow (a concept that is, admittedly, not well defined), a payload length, a next header field saying what type of header follows, a hop limit, and 128-bit source and destination addresses, against 32 bits for IPv4.

What IPv6 removed is as interesting as what it kept:

The next header field and that chain deserve a closer look, because together they are the speed win. If next header is 6, 17, or 58, meaning the Transmission Control Protocol (TCP), the User Datagram Protocol (UDP), or the Internet Control Message Protocol for IPv6 (ICMPv6), then Layer 4 begins at byte 40 and a router needs no further reading. Otherwise the router follows the next header chain, since extension headers come first. The division of labor is the point: a router must read only the hop-by-hop extension header, and the remaining extension headers are end to end, which is to say they are the destination host's problem rather than a router's.

Adoption: roughly half of Google's clients now reach its services over IPv6, and the National Institute of Standards and Technology reports that a third of United States government domains are IPv6 capable. That progress represents more than 25 years of deployment, and counting. Compare what the application layer produced over the same period: the web, social media, streaming media, gaming, and telepresence. Why the difference? Because every router and host along a path must understand a new network-layer protocol, and no one can upgrade the core of the network all at once. One developer shipping code can change the application layer; the network layer admits no such move.

The problem, and autonomous systems

We want to send packets from one subnet to another, and there are two cases, distinguished not by distance but by ownership.

In the first case, source and destination belong to the same organization, meaning that one group controls the routing of the whole network. That organization might be an Internet service provider (ISP), a large company, or a college. Dartmouth runs a large network of many routers connecting many groups across campus: computer science, Thayer, biology, chemistry, government. Such an organization-controlled network is an autonomous system (AS), and OSPF computes routes within it.

In the second case, source and destination belong to different organizations, and BGP routes between autonomous systems. Roughly 120,000 autonomous systems exist in the world today. In 1995 there were about 3,000.

A concrete version of the problem. PC1 at 192.168.1.5 wants to reach PC2 at 10.1.1.5, on a different subnet in the same AS, with routers R1, R2, and R3 in between. Some of this we already know how to do:

The middle is what remains: R1 and R3 have no idea how to reach 10.1.1.0/24, and nothing they can observe locally will tell them. That gap is what routing protocols fill.

Two ways to build a control plane

Recall the split from last class. Forwarding moves a packet from a router's input port to the appropriate output port, and is the data plane. Routing determines the route a packet takes from source to destination, and is the control plane. Today is about the second.

The data plane is identical under both approaches below: given a destination address, forward the packet out the port that leads there. What differs is who computes the table.

Per-router control plane: individual routing algorithm components in each and every router interact, the routers communicate among themselves, and each router computes its own forwarding table. This arrangement is traditional routing, which is to say OSPF and BGP.

SDN control plane: a logically separate remote controller computes the forwarding tables and passes them to each router. The controller monitors the entire network, takes input from routers observing traffic, and updates the tables on each router. Each router runs a control agent with limited functionality, which communicates with the controller and takes no part in computing the table.

Most of today concerns the first approach, and we return to the second at the end.

Graph abstraction and link costs

A routing protocol's goal is to determine good paths from sending hosts to receiving hosts through the network of routers, where a path is the sequence of routers a packet traverses, and good might mean least cost, fastest, or least congested. Routing is one of the classic networking challenges.

Model the network as an undirected graph G = (N, E), where N is the set of routers and E is the set of links. Write ca,b for the cost of the direct link connecting a and b, with ca,b = ∞ when a and b are not direct neighbors.

The important thing about cost is that the network operator defines it. A cost could be 1 for every link, or inversely related to bandwidth, or inversely related to congestion. The routing algorithm optimizes whatever you tell it to optimize, which means that "shortest path" is only as meaningful as the cost metric behind it. That point matters again when we reach traffic engineering.

Link state and distance vector

Routing algorithms divide along two axes. First, by what information they use:

Second, by how fast routes change: static routes change slowly over time, while dynamic routes change more quickly, updating periodically or in response to changes in link cost.

OSPF is a link-state protocol, which is where we focus.

Dijkstra's algorithm

A link-state algorithm assumes that all nodes know the topology and link costs, which a link-state broadcast accomplishes, so that every node ends up with the same information. Each node then computes least-cost paths from itself to every other node, and those paths give that node its forwarding table. The algorithm is iterative: after k iterations a node knows the least-cost path to k destinations.

Notation:

The algorithm, computing from source u: 

Initialization:
  N' = {u}
  for all nodes v
    if v adjacent to u
      then D(v) = c(u,v)
      else D(v) = infinity

Loop
  find node w not in N' such that D(w) is a minimum
  add w to N'
  update D(v) for all v adjacent to w and not in N':
     D(v) = min( D(v), D(w) + c(w,v) )
until all nodes in N'

The update line is the heart of the algorithm: the new least-cost path to v is either the old one, or the known least-cost path to w plus the direct cost from w to v.

All of this should look familiar from CS 10. Note one special case: when all edges have the same weight, Dijkstra's algorithm is unnecessary, because a breadth-first search suffices.

A worked example

Take the graph with these link costs:

cu,v=2, cu,x=1, cu,w=5, cv,x=2, cv,w=3, cx,w=3, cx,y=1, cw,y=1, cw,z=5, cy,z=2

Running from u, and watching D(w) in particular:

Notice that D(w) went 5 → 4 → 3. The direct link from u to w exists and costs 5, and it is the worst of the three options. An initial estimate is a starting point, not an answer.

The result is a least-cost-path tree rooted at u, which converts to a forwarding table: 

destination    outgoing link
    v              (u,v)
    x              (u,x)
    y              (u,x)
    w              (u,x)
    z              (u,x)

So u routes to v directly and everything else by way of x. Does the router need to keep the whole tree? No, because it needs only the next hop for each destination. Every other router builds a similar table from its own perspective, and packets find their way because each router's local decision is consistent with a globally computed tree.

Complexity

With n nodes, each of n iterations must check all nodes not yet in N', which gives n(n+1)/2 comparisons, or O(n2). An implementation using a priority-queue heap does better, at O(e log n).

A second cost matters here that a normal algorithms course would not raise: message complexity. Every router must broadcast its link state to the other n routers, and each router's message crosses O(n) links, so the overall message complexity is O(n2). Computation is cheap, and flooding the network with state is not. That cost is why the next section exists.

Making routing scalable

Everything so far has been idealized: all routers identical, the network flat. Neither assumption holds in practice, for two reasons.

Scale. Billions of destinations exist. No router can store them all in a routing table, and the message exchange needed to maintain such tables would swamp the links.

Administrative autonomy. The Internet is a network of networks, and each network's administrators want to control routing within their own network.

The Internet's answer to both is hierarchy: aggregate routers into autonomous systems, also called domains. Within an AS, all routers run the same intra-domain protocol and hold information about each other. Routers in different autonomous systems can run entirely different intra-domain protocols, and nobody outside needs to know or care. A gateway router sits at the edge of its AS with links to routers in other autonomous systems, and performs inter-domain routing as well as intra-domain routing. Each AS gets its own number, which the Internet Assigned Numbers Authority (IANA) assigns through the five regional Internet registries: AFRINIC for Africa, ARIN for North America, APNIC for the Asia Pacific region, LACNIC for Latin America and the Caribbean, and RIPE for Europe, the Middle East, and parts of Central Asia.

Intra-AS routing uses OSPF, and inter-AS routing uses BGP.

Other intra-AS protocols exist and are worth recognizing. The Routing Information Protocol (RIP), in RFC 1723, is classic distance vector, exchanging distance vectors every 30 seconds; it is no longer widely used. The Enhanced Interior Gateway Routing Protocol (EIGRP) is also distance-vector based, and was Cisco-proprietary for decades before becoming open in 2013 in RFC 7868. OSPF, in RFC 2328, is link state. IS-IS, pronounced "eye ess, eye ess," is a standard from the International Organization for Standardization (ISO) rather than an RFC standard, and is essentially the same as OSPF.

OSPF: routing within an autonomous system

"Open" means publicly available. OSPF is a classic link-state algorithm: each router floods link-state advertisements (LSAs) to all other routers in the entire AS, builds a full topology of the AS, and runs Dijkstra's algorithm to compute its forwarding table. Multiple cost metrics are possible, such as bandwidth and delay.

One implementation detail is worth noticing. OSPF sends its messages directly over IP rather than over TCP or UDP, using protocol number 89; recall that TCP is 6 and UDP is 17. So OSPF is a Layer 3 protocol carried in IP datagrams, like ICMP, rather than an application riding on a transport protocol. (Recall that the Internet Control Message Protocol, ICMP, sits at Layer 3 for the same kind of reason.) It is part of the network's own machinery.

On security: all OSPF messages carry a sequence number to prevent replay attacks, and a router can authenticate them to prevent malicious intrusion, using an MD5 (message digest 5) hash. MD5 was a reasonable choice when the protocol was written and is not one now. We discuss why in the cryptography unit.

How a router joins and converges

Each router in an AS has a unique identifier and runs the OSPF protocol. Four steps take a newly connected router from knowing nothing to holding a complete forwarding table.

  1. Become neighbors. A new router sends a Hello message to its directly connected neighbors; they reply; now they know about each other.
  2. Exchange databases. Neighbors exchange information about every network known to them.
  3. Flood on change. When something changes, such as a new link, a link failing, or a link returning to service, a router tells its neighbors with an LSA; they tell their neighbors; and so forth. That propagation is LSA flooding, and it is how every router ends up with the same view.
  4. Calculate best routes. After flooding, every router holds an identical link-state database (LSDB) for the whole AS: a graph of every link in the system, with costs. Each router builds a graph from its own LSDB and runs Dijkstra's algorithm to find shortest paths from itself to everywhere else.

Where do the costs come from? An LSA carries a metric computed as

cost = reference bandwidth / link bandwidth

with the reference bandwidth commonly 100 Mbps. So a 10 Mbps link has cost 10 and a 100 Mbps link has cost 1, which makes faster links cheaper, so that Dijkstra's algorithm prefers them. Here is the concrete version of "the operator defines cost."

Areas

OSPF does not scale well on its own, for exactly the message-complexity reason above: a large network generates enormous LSA traffic between routers. The fix is another layer of hierarchy. Each router is assigned to an area and communicates within it, and a backbone area, area 0, connects the areas. Inter-area routing must pass through area 0. Hierarchy inside the AS, mirroring the hierarchy of autonomous systems inside the Internet.

BGP: routing between autonomous systems

Autonomous systems are large organizations: ISPs such as AT&T, Verizon, and NTT, along with big companies and universities. Each one controls routing within its own borders and often holds large blocks of IP address space. Gateway routers connect them.

A router's forwarding table entries have the form (x, I), where x is a network address or subnet and I is a router port number, and both algorithms populate the table: intra-AS routing determines the entries for destinations within the AS, and inter-AS routing determines the entries for external destinations. Recall from last class how the router then uses such a table: it selects the port whose network and subnet mask give the longest match on the destination address, falling back to the default entry 0.0.0.0/0 when nothing more specific matches.

The inter-domain problem for AS1 is to learn which destinations are reachable through AS2 and which through AS3, and then to propagate that reachability information to all routers in AS1. When an internal router receives a datagram destined outside AS1, it needs to know to which gateway router it should send the datagram.

BGP is the de facto inter-domain routing protocol, the glue that holds the Internet together. It lets a subnet advertise its existence and the destinations it can reach to the rest of the Internet: "I am here, here is who I can reach, and how." Specifically, BGP gives each AS a way to obtain reachability information from neighboring autonomous systems (eBGP), to determine routes based on that information and on policy, to propagate reachability information to all AS-internal routers (iBGP), and to advertise its own network to its neighbors.

Every router in an AS is either a gateway router, connecting to other autonomous systems and running both eBGP and iBGP, or an internal router, connecting to other routers and hosts in the same AS. Note that an inter-AS protocol requires coordination among several organizations, so communicating autonomous systems must run the same protocol. On the Internet they all run BGP.

Sessions and messages

A BGP session is two BGP routers, called peers, exchanging messages over a semi-permanent TCP connection on port 179. Note the contrast: BGP runs over TCP, unlike OSPF with its raw IP, because BGP needs reliable delivery of advertisements between parties that may be far apart.

Four message types:

Path advertisement

BGP is a path vector protocol: it advertises complete paths to destination prefixes rather than distances. An advertised route is a prefix plus attributes, of which two matter most:

Follow a prefix X, which lives in AS3, as it propagates:

  1. AS3's gateway 3a advertises the path "AS3, X" to AS2's gateway 2c by way of eBGP. In doing so, AS3 promises AS2 that it will forward datagrams toward X.
  2. Based on AS2's policy, 2c accepts the path and propagates it to all AS2 routers by way of iBGP.
  3. Based on AS2's policy, gateway 2a advertises "AS2, AS3, X" to AS1's gateway 1c by way of eBGP. Note that AS2 has prepended itself to the path.

A gateway may learn several paths to the same destination. In the example, AS1's gateway 1c learns "AS2, AS3, X" from 2a and also learns "AS3, X" directly from 3a. Based on policy, it chooses "AS3, X" and advertises that path within AS1 by way of iBGP.

That word policy keeps appearing, and it is the substance of BGP. A gateway receiving an advertisement applies an import policy to accept or decline the path, for instance never routing through some AS Y, and its policy also determines whether to advertise the path onward to other neighbors. An AS can decline a perfectly good route, and can refuse to tell anyone about a route it is using itself.

From an advertisement to a table entry

One step remains between learning a path and forwarding a packet, and it is where the two protocols meet. Internal routers 1a, 1b, and 1d learn by way of iBGP that the path to X goes through gateway 1c. That fact alone does not tell them which of their own ports to use, so each one asks its intra-domain routing: at 1d, OSPF says that reaching 1c means using interface 1, so 1d installs the entry (X, 1). At 1a, OSPF says that reaching 1c means using interface 2, so 1a installs the entry (X, 2). Same destination, same BGP advertisement, different port numbers, because the two routers sit in different places inside AS1. BGP supplies the gateway and OSPF supplies the local direction to it.

Hot potato routing

Suppose AS2's internal router 2d learns by way of iBGP that it can reach X through either gateway 2a or gateway 2c, and the intra-domain OSPF costs to those gateways are 201 and 263. Which does it choose?

Hot potato routing: pick the local gateway with the least intra-domain cost, which is 2a at 201, even if that path involves more AS hops to reach X. Do not worry about the inter-domain cost at all.

The logic is unsentimental: the cost you pay is the cost of carrying the packet across your own network, so minimize that cost and hand the packet off as soon as possible. What happens after the packet leaves is someone else's expense. Real BGP route selection is more complex than pure hot potato routing, and is based on it.

Table sizes

How large do forwarding tables get? Real BGP routing tables may hold over half a million entries. Roughly:

Home or enterprise router: 10–500 entries
Regional ISP: 1,000–100,000 entries
Tier 1 ISP or backbone: about 1,000,000, meaning all of them

Your virtual machine (VM) has four, which ip route will show: 

$ ip route
default via 192.168.159.2 dev eth0 proto dhcp src 192.168.159.129 metric 100
172.17.0.0/16 dev docker0 proto kernel scope link src 172.17.0.1 linkdown
192.168.159.0/24 dev eth0 proto kernel scope link src 192.168.159.129 metric 100
192.168.159.2 dev eth0 proto dhcp scope link src 192.168.159.129 metric 100

A default route by way of 192.168.159.2, plus directly connected entries for the Docker network and the local subnet. Anything not matching a specific entry follows the default, which is what a host does instead of participating in routing at all.

Putting it all together

Everything from Day 4 onward now assembles into one story. Suppose you are standing up a company network, ignoring network address translation for simplicity:

  1. Contact an ISP. Install a gateway router connecting to the ISP's gateway router. The ISP gives you an IP address range, say a /24, which holds 254 hosts.
  2. The ISP's AS propagates by way of BGP that your network exists, so the rest of the Internet learns that your network is reachable through them.
  3. Set up servers, meaning web, mail, and Domain Name System (DNS) servers, giving each an address from your range, and give your gateway router one as well.
  4. OSPF computes routes among your own hosts and gateway.
  5. Get a domain name from a registrar, supplying the addresses of your web and mail servers. The registrar creates the DNS A and MX (mail exchange) records. Now people can find you.

And the reverse direction, when Alice wants to visit cs60.edu:

  1. Alice makes a DNS request to get your web server's IP address.
  2. She makes a HyperText Transfer Protocol (HTTP) GET request to that address on port 80.
  3. Her router matches the destination address and sends the packet toward her ISP. From BGP, Alice's ISP knows that your ISP controls that address block, and knows the path to their AS. If your ISP got its block from a larger ISP, Alice's ISP routes to the larger ISP, which routes to yours.
  4. Your ISP knows that you hold that address and routes the request out the port connected to your gateway router, which uses OSPF to reach the web server.
  5. The web server sends back the page, and the process reverses.

DNS, HTTP, TCP, IP, longest prefix matching, OSPF, and BGP, all in one page load.

The SDN control plane

Now the alternative. Start with the problem that motivates it.

Traffic engineering is hard with traditional routing

Three questions an operator might reasonably ask, and the answers traditional routing gives.

Suppose the operator wants u-to-z traffic to flow along u→v→w→z rather than the u→x→y→z path that Dijkstra's algorithm computes. The only way to get it is to redefine the link weights until the algorithm happens to produce the desired result, or to write a new routing algorithm. Link weights are the only control knobs available, and they are a blunt instrument, because changing one weight to fix one path changes every other path that uses that link.

Suppose instead the operator wants to split u-to-z traffic across both paths, to balance the load. Traditional routing cannot do it without a new routing algorithm.

Suppose w wants to route two classes of traffic differently on the way to z. Destination-based forwarding cannot do that either, since the destination is the same in both cases.

Generalized forwarding, from last class, can achieve any of these, because it can match on any header field in any layer rather than on the destination address alone. SDN is what puts that capability under coordinated control.

The four ideas, and the architecture

SDN restructures the control plane around four ideas:

  1. Generalized flow-based forwarding in the data plane, OpenFlow for example.
  2. Separation of the control and data planes.
  3. Control plane functions external to the data-plane switches, running on a remote controller.
  4. Programmable control applications, such as routing, load balancing, and access control, written against the controller's interface.

The architecture stacks in three layers, with an interface at each boundary.

Data-plane switches are fast, simple, commodity devices implementing generalized forwarding in hardware. The controller supervises the computation and installation of their flow tables through an interface such as OpenFlow, which defines exactly what is controllable and what is not, and which also serves as the protocol for communicating with the controller.

The SDN controller, a network operating system, maintains network state information and interacts with control applications above it through a northbound interface and with switches below it through a southbound interface. The controller is itself implemented as a distributed system, for performance, scalability, fault tolerance, and robustness. A logically centralized controller need not be a physically centralized one, which is what keeps it from being a single point of failure.

Network-control applications are the brains of the operation, implementing control functions using the lower-level services the controller provides. Crucially they are unbundled: a third party can write them, distinct from both the switch vendor and the controller vendor. That change to the industry is as much of what SDN represents as the technical change. Open Daylight is one such controller platform.

Inside the controller are three layers. An interface layer of abstractions and interfaces, often following representational state transfer (REST), serves the control applications. Network-wide state management holds the state of links, switches, and services as a distributed database, along with the network graph, the flow tables, and statistics. A communication layer speaks OpenFlow and the Simple Network Management Protocol (SNMP) to the controlled devices.

A link failure, end to end

Watch a single event flow through the whole architecture:

  1. Switch s1 experiences a link failure and notifies the controller with an OpenFlow port status message.
  2. The controller receives the message and updates its link status information.
  3. The Dijkstra link-state routing application, which previously registered to be called whenever link status changes, is called.
  4. It accesses the network graph and link-state information in the controller and computes new routes.
  5. It interacts with the controller's flow-table-computation component, which computes the new flow tables needed.
  6. The controller uses OpenFlow to install those tables in the switches that need updating.

Note what just happened: the same algorithm from earlier today, but running once in one place, with a complete view, as an application anyone could have written, rather than running separately in every router, each assembling its own view by flooding.

Exercises

Complete these before or around the next class.

  1. Trace the autonomous systems along a real path. Download as_explorer.py and the .txt files from the file list above. Each .txt file holds the output of a traceroute run like this one, where -n prints numeric IP addresses rather than hostnames: 
    $ traceroute -n google.com > google.txt

    Run a traceroute to your own favorite website and redirect it to a .txt file in the same directory. Then run as_explorer.py, which examines every .txt file in its directory, looks up the AS controlling each IP address through Team Cymru, falling back to the RADb registry when Team Cymru has no answer, and prints details about the autonomous systems along each route.

    Then answer these questions:

    • How many router hops did your trace take, and how many autonomous systems did it cross? Why is the second number so much smaller than the first?
    • Who owns each AS on your path, and what kind of organization is it? Label each one as a campus, a research network, an ISP or transit provider, or a content provider. Look up any name you do not recognize.
    • Did the path end in the AS of the company that runs your site? If not, whose AS was it?
    • Find a hop that as_explorer.py marked [registry], or one with no AS at all. Why could BGP not tell us who owns that address?
    • Which autonomous systems do all of your group's paths pass through? If one of them went down, what would happen to your access?
    • Where do your paths diverge, which organization makes that choice, and what information does that AS have available to make it?
    • These AS paths depend on agreements between organizations rather than on which route is physically shortest. Find an example in your group's output that supports that claim.
  2. Run Dijkstra's algorithm by hand on the example graph from source x rather than u, and write out x's forwarding table. Which destinations does x reach through u?
  3. Compute OSPF costs for a 1 Gbps link, a 100 Mbps link, and a 10 Mbps link, with a reference bandwidth of 100 Mbps. What problem do you notice with links faster than the reference bandwidth, and how would you fix it?
  4. Run ip route on your VM and identify which entry each of these destinations matches: 192.168.159.50, 172.17.0.9, and 142.251.32.100.
  5. In the hot potato example, work out which gateway 2d would choose if the OSPF weights were reversed. Then explain why AS2 might be perfectly happy with a route that is worse for the packet overall.
  6. Look up the current number of active BGP entries at the potaroo link in the references above and compare it to the figure of about 1,000,000 from the slides. Is the table still growing?

Terms

Not a comprehensive reference — the textbook has much more — but these are the terms from Day 8 that recur throughout the course.

IPv6
The successor to IPv4, motivated by address exhaustion, with 128-bit addresses and a fixed 40-byte header. It drops the checksum, fragmentation, and in-header options. About half of Google's clients now reach it over IPv6, after more than 25 years of deployment.
extension header
An optional IPv6 header chained after the fixed base header, replacing IPv4's in-header options. A next header value of 6, 17, or 58 means Layer 4 starts at byte 40; otherwise a router follows the chain. Routers read only the hop-by-hop extension header, and the rest are end to end, which is the speed gain.
autonomous system (AS)
A network under the routing control of one organization, with its own AS number assigned by IANA through the regional registries. About 120,000 exist today, up from 3,000 in 1995.
default gateway
The router a host sends to when the destination address is not on its own subnet, learned from DHCP along with its address and mask.
intra-domain versus inter-domain routing
Routing within one AS, by OSPF, RIP, EIGRP, or IS-IS, against routing between autonomous systems, by BGP. Different autonomous systems may use different intra-domain protocols.
gateway router
A router at the edge of an AS with links into other autonomous systems, performing both inter-domain and intra-domain routing.
control agent
The limited-function component in an SDN-controlled router that communicates with the controller and takes no part in computing the forwarding table.
link cost
The weight assigned to a link, which the network operator defines: constant, inversely related to bandwidth, or inversely related to congestion. It determines what "shortest path" means.
link state versus distance vector
Link-state algorithms give every router complete topology and cost information, as OSPF does; distance-vector algorithms have routers compute iteratively from information exchanged with neighbors, as RIP and EIGRP do.
Dijkstra's algorithm
Computes least-cost paths from one source to all other nodes, adding the cheapest not-yet-finalized node each iteration and updating its neighbors' estimates. O(n2) naively, O(e log n) with a heap. A breadth-first search suffices when all edges have equal weight.
message complexity
The cost of disseminating routing information, distinct from computational complexity. For link-state flooding it is O(n2), which is what limits how large a flat routing domain can be.
OSPF (Open Shortest Path First)
The standard intra-AS link-state protocol, in RFC 2328. It floods LSAs directly over IP using protocol 89, builds a full AS topology in the LSDB, and runs Dijkstra's algorithm. Messages carry sequence numbers and can be authenticated with an MD5 hash.
LSA (link-state advertisement) and LSA flooding
The message announcing a link change, propagated neighbor to neighbor until every router in the AS holds an identical view.
LSDB (link-state database)
A router's copy of the graph of the entire AS, from which it computes its own shortest paths. Identical across all routers once flooding converges.
OSPF cost metric
Reference bandwidth divided by link bandwidth, with the reference commonly 100 Mbps, so a 10 Mbps link costs 10 and a 100 Mbps link costs 1.
OSPF area and backbone area
A subdivision of an AS that limits LSA traffic, with area 0, the backbone, connecting the areas. Inter-area routing passes through area 0.
BGP (Border Gateway Protocol)
The de facto inter-domain routing protocol, in RFC 4271, running over semi-permanent TCP connections on port 179. A path vector protocol: it advertises complete AS paths, which policy then filters and selects among.
eBGP and iBGP
eBGP obtains reachability information from neighboring autonomous systems; iBGP propagates it to all routers inside the AS. Gateway routers run both.
BGP messages
OPEN, which opens and authenticates the session; UPDATE, which advertises or withdraws a path; KEEPALIVE, which maintains the session and acknowledges an OPEN; and NOTIFICATION, which reports errors and closes the session.
AS-PATH
The BGP attribute listing the autonomous systems an advertisement has traversed. Each AS prepends itself before passing the advertisement along.
NEXT-HOP
The BGP attribute identifying the specific internal router leading to the next-hop AS. An internal router combines it with intra-domain routing to get an actual port number.
import policy
A gateway's rules for accepting or declining an advertised path, such as never routing through a particular AS. An AS policy also determines whether to advertise a path onward to other neighbors.
hot potato routing
Choosing the local gateway with the least intra-domain cost, regardless of the inter-domain path length, which minimizes the cost you bear rather than the total cost.
traffic engineering
Steering traffic along chosen paths. Difficult under traditional routing, because link weights are the only control knob, changing one affects every path using that link, and neither load balancing across paths nor treating traffic classes differently is possible at all.
SDN controller
A network operating system maintaining network-wide state, exposing a northbound interface to control applications and a southbound interface to switches. Logically centralized, though implemented as a distributed system.
northbound and southbound interfaces
The interface from the controller up to network-control applications, and the interface from the controller down to the controlled devices, such as OpenFlow and SNMP.
network-control application
Software implementing a control function, such as routing, load balancing, or access control, on top of the controller's interface. Unbundled, meaning a third party can supply it.

Credit: Most information on this page is from Computer Networking: A Top-Down Approach, 9th edition by Kurose and Ross.
This page was generated by Claude from in-class slides.