Tip: If anyone want to speed up the lecture videos a little, inspect
the page, go to the browser console, and paste this in:
document.querySelector('video').playbackRate = 1.2
Abstract graph model of a computer network
* Given any two nodes x and y, there are typically many paths between
the two nodes, with each path having a cost.
* One or more of these paths is a least-cost path.
1.3.2 Routing protocols
A routing protocol specifies how routers communicate information
that enables them to select routes between any two nodes on a computer
network.
Routers perform the “traffic directing” functions on the
Internet.
Data packets are forwarded through the networks of the internet from
router to router until they reach their destination computer.
Routing algorithms determine the specific choice of route.
Each router has prior knowledge only of networks attached to it
directly.
A routing protocol shares this information first among immediate
neighbors, and then throughout the network.
This way, routers gain knowledge of the topology of the
network.
The ability of routing protocols to dynamically adjust to changing
conditions, such as disabled data lines or computers, and still route
data around obstructions is what gives the Internet its survivability
and reliability.
The specific characteristics of routing protocols include:
the manner in which they avoid routing loops,
the manner in which they select preferred routes,
The protocols use information about
* hop costs,
* the time they require to reach routing convergence,
* their scalability, and
* other factors.
Convergence is the state of a set of routers that have the same
topological information about the inter-network in which they
operate.
For a set of routers to have converged, they must have collected all
available topology information from each other via the implemented
routing protocol, the information they gathered must not contradict any
other router’s topology information in the set, and it must reflect the
real state of the network.
In a converged network all routers “agree” on what the network
topology looks like.
All Interior Gateway Protocols rely on convergence to function
properly.
To have converged, is a normal state of an operational autonomous
system (AS).
The Exterior Gateway Routing Protocol, BGP, typically never
converges, because the Internet is too big for changes to be
communicated fast enough.
When a routing protocol process is enabled, every participating
router will attempt to exchange information about the topology of the
network.
The extent of this information exchange, the way it is sent and
received, and the type of information required vary widely depending on
the routing protocol in use, see e.g. RIP, OSPF, BGP4.
A state of convergence is achieved once all routing
protocol-specific information has been distributed to all routers
participating in the routing protocol process.
Any change in the network that affects routing tables will break the
convergence temporarily until this change has been successfully
communicated to all other routers.
Different protocols for inter-domain/AS versus
intra-domain/AS routing:
1.3.5 Networks of networks
40.000-50,000 AS/domains in the internet today:
See http://bgp.potaroo.net/index-as.html for reports on the
evolution of the number of Autonomous Systems over time.
1.3.5.1 Autonomous system (AS)
https://en.wikipedia.org/wiki/Autonomous_system_(Internet)
An autonomous system (AS) is a collection of connected Internet Protocol
(IP) routing prefixes under the control of one or more network operators
on behalf of a single administrative entity or domain that presents a
common, clearly defined routing policy to the internet.
A routing domain is a collection of networked systems that operate
common routing protocols, and are under the control of a single
administration.
For example, this might be a set of routers under a control of a
single organization, some of them operating a corporate network, some
others a branch office network, and the rest the data center
network.
A given autonomous system can contain multiple routing domains, or a
set of routing domains can be coordinated without being an
Internet-participating autonomous system.
Although there are many types of routing protocols, three major
classes are in widespread use on IP networks:
Interior gateway protocols type 1, link-state routing protocols,
such as OSPF and IS-IS
Interior gateway protocols type 2, distance-vector routing
protocols, such as Routing Information Protocol, RIPv2, IGRP.
Exterior gateway protocols are routing protocols used on the
Internet for exchanging routing information between Autonomous Systems,
such as Border Gateway Protocol (BGP), Path Vector Routing
Protocol.
In a decentralized routing algorithm, the
calculation of the least-cost path is carried out in an iterative,
distributed manner.
No node has complete information about the costs of all network
links.
Instead, each node begins with only the knowledge of the costs of
its own directly attached links.
Through an iterative process of calculation and exchange of
information with its neighboring nodes (that is, nodes that are at the
other end of links to which it itself is attached), a node gradually
calculates the least-cost path to a destination or set of
destinations.
Distance-vector (DV) algorithm
In these protocols, each router does not possess information about
the full network topology.
It advertises its distance value (DV) calculated to other routers
and receives similar advertisements from other routers unless changes
are done in local network or by neighbours (routers).
Using these routing advertisements each router populates its routing
table.
In the next advertisement cycle, a router advertises updated
information from its routing table.
This process continues until the routing tables of each router
converge to stable values.
A centralized global routing algorithm computes the
least-cost path between a source and destination using complete, global
knowledge about the network.
That is, the algorithm takes the connectivity between all nodes and
all link costs as inputs.
Link-state methods broadcast connectivity information to all nodes
in the network, and then centrally perform Dijkstra’s
algorithm to find the shortest path on a graph
Least cost path and forwarding table for nodule u
In link-state routing protocols, each router possesses information
about the complete network topology.
Each router then independently calculates the best next hop from it
for every possible destination in the network using local information of
the topology.
The collection of best-next-hops forms the routing table.
This contrasts with distance-vector routing protocols, which work by
having each node share its routing table with its neighbors.
In a link-state protocol, the only information passed between the
nodes is information used to construct the connectivity maps.
Hierarchical routing: paths between interconnected autonomous systems
(AS)
Autonomous systems (AS) consist of a group of
routers typically under the same administrative control
(e.g., operated by the same ISP or belonging to the same company
network).
Routers within the same AS all run the same routing algorithm and
have information about each other.
The routing algorithm running within an autonomous system is called
an intra-autonomous system routing protocol.
Obtaining reachability information from neighboring ASs and
propagating the reachability information to all routers internal to the
AS, are handled by the inter-AS routing protocol.
Since the inter-AS routing protocol involves communication between
two ASs, the two communicating ASs must run the same inter-AS routing
protocol.
In the Internet all ASs run the same inter-AS routing protocol,
called BGP4
1.4.4 Centralized control (software
defined networking)
Classic model: Fascinating and robust distributed algorithm runs on
each router:
Meh… SDN: Just centralize the computation:
1.5 Internet routing at the global
scale
Actual internet algorithms
06-NetworkControl/dynamic-routing-protocols.png
A very important difference between intra-domain and inter-domain
routing are the routing policies that are used by each domain.
Inside a single domain, all routers are considered equal, and when
several routes are available to reach a given destination prefix, the
best route is selected based on technical criteria such
as
the route with the shortest delay,
the route with the minimum number of hops, or
the route with the highest bandwidth.
When we consider the interconnection of domains that are managed by
different organizations, this is no longer true.
Each domain implements its own routing policy.
A routing policy is composed of three elements (more below):
an import filter that specifies which routes can be accepted by a
domain,
an export filter that specifies which routes can be advertised by a
domain, and
a ranking algorithm that selects the best route when a domain knows
several routes towards the same destination prefix.
As we will see later, another important difference is that the
objective of the inter-domain routing protocol is to find the cheapest
route towards each destination.
An interior gateway protocol (IGP) is a type of protocol used for
exchanging routing information between gateways (commonly routers)
within an autonomous system (for example, a system of corporate local
area networks).
This routing information can then be used to route network-layer
protocols like IP
Each router maintains a RIP table known as a routing table.
A router’s routing table includes both the router’s distance vector
and the router’s forwarding table.
Distributed: Routing Information Protocol (RIP)
The Routing Information Protocol (RIP) is one of the oldest
distance-vector routing protocols, which employs the hop count as a
routing metric.
RIP prevents routing loops, by implementing a limit on the number of
hops allowed in a path from source to destination.
The largest number of hops allowed for RIP is 15, which limits the
size of networks that RIP can support.
In RIPv1 routers broadcast updates with their routing table every 30
seconds.
In the early deployments, routing tables were small enough that the
traffic was not significant.
As networks grew in size, however, it became evident there could be
a massive traffic burst every 30 seconds, even if the routers had been
initialized at random times.
In most networking environments, RIP is not the preferred choice of
routing protocol, as its time to converge and scalability are poor
compared to EIGRP, OSPF, or IS-IS.
The best thing about RIP jokes is that they’re funny 15 more
times…
The strange thing about BGP jokes is that they’re borderline
funny but everybody repeats them anyway.
Border Gateway Protocol version 4 (BGP4)
I would tell a BGP joke, but everyone probably already knows
it.
BGP provides each A.S. a means to:
Obtain sub-net reachability information from neighboring ASs.
Propagate the reachability information to all routers internal to
the AS.
Determine “good” routes to sub-nets based on the reachability
information and on AS policy.
Most importantly, BGP allows each sub-net to advertise its existence
to the rest of the Internet.
A sub-net screams “I exist and I am here,” and BGP makes sure that
all the ASs in the Internet know about the sub-net and how to get
there.
If it weren’t for BGP, each sub-net would be isolated, alone and
unknown by the rest of the Internet.
Border Gateway Protocol version 4 (BGP4)
BGP session that spans two ASs is called an external BGP (eBGP)
session
BGP session between routers in the same AS is called an internal
BGP (iBGP) session
I’d like to tell you a full joke about a BGP table, but I don’t think
you can remember it all.
1.5.2.3 Politics and money!
Why is this a sub-heading under Exterior gateway protocols??
1.5.2.3.1 Types of domain
Each domain contains a set of routers.
From a routing point of view, these domains can be divided into two
classes:
A transit domain is a domain that provides a
transit service for other domains, i.e. the routers in this domain
forward packets whose source and destination do not belong to the
transit domain.
A stub domain sends and receives packets whose
source or destination are one of its own hosts.
As of this writing, about 85% of the domains in the Internet are
stub domains.
A stub domain that is connected to a single transit domain is called
a single-homed stub.
A multi-homed stub is a stub domain connected to two or more transit
providers.
The stub domains can be further classified by considering whether
they mainly send or receive packets.
An access-rich stub domain is a domain that contains hosts that
mainly receive packets.
Typical examples include small ADSL- or cable modem-based Internet
Service Providers or enterprise networks.
On the other hand, a content-rich stub domain is a domain that
mainly produces packets.
Examples of content-rich stub domains include google, yahoo,
microsoft, facebook or content distribution networks such as akamai or
limelight
For the last few years, we have seen a rapid growth of these
content-rich stub domains.
06-NetworkControl/stub-transit-domains.png
1.5.2.3.2 Non-technical routing
decisions
In the early days of the Internet, domains would simply exchange all
the routes they know to allow a host inside one domain to reach any host
in the global Internet.
However, in today’s highly commercial Internet, this is no longer
true as inter-domain routing mainly needs to take into account the
economical relationships between the domains.
Furthermore, while intra-domain routing usually prefers some routes
over others based on their technical merits (e.g. prefer route with the
minimum number of hops, prefer route with the minimum delay, prefer high
bandwidth routes over low bandwidth ones, etc) inter-domain routing
mainly deals with economical issues.
For inter-domain routing, the cost of using a route is often more
important than the quality of the route measured by its delay or
bandwidth.
1.5.2.3.3 Types of
relationship
There are different types of economic relationships that can exist
between domains.
Inter-domain routing converts these relationships into peering
relationships between domains that are connected via peering links.
customer->provider
Such a relationship is used when a customer domain pays an Internet
Service Provider to be able to exchange packets with the global Internet
over an inter-domain link.
A similar relationship is used when a small Internet Service
Provider pays a larger Internet Service Provider to exchange packets
with the global Internet.
shared-cost peering
Such a relationship usually does not involve a payment from one
domain to the other in contrast with the customer->provider
relationship.
A shared-cost peering relationship is usually established between
domains having a similar size and geographic coverage. For example,
consider the figure above.
If AS3 and AS4 exchange many packets via AS1, they both need to pay
AS1.
A cheaper alternative for AS3 and AS4 would be to establish a
shared-cost peering.
Such a peering can be established at IXPs where both AS3 and AS4 are
present or by using private peering links.
This shared-cost peering should be used to exchange packets between
hosts inside AS3 and hosts inside AS4.
However, AS3 does not want to receive on the AS3-AS4 shared-cost
peering links packets whose destination belongs to AS1 as AS3 would have
to pay to send these packets to AS1.
sibling
Such a relationship is used when two domains exchange all their
routes in both directions.
In practice, such a relationship is only used between domains that
belong to the same company.
These different types of relationships are implemented in the
inter-domain routing policies defined by each domain.
The inter-domain routing policy of a domain is composed of three
main parts:
the import filter that specifies, for each
peering relationship, the routes that can be accepted from the
neighboring domain (the non-acceptable routes are ignored and the domain
never uses them to forward packets)
the export filter that specifies, for each
peering relationship, the routes that can be advertised to the
neighboring domain
the ranking algorithm that is used to select the
best route among all the routes that the domain has received towards the
same destination prefix
1.6 Which layer does routing
use?
Routing protocols, according to the OSI routing framework, are layer
management protocols for the network layer, regardless of their
transport mechanism:
IS-IS runs on the data link layer (Layer 2)
Open Shortest Path First (OSPF) is encapsulated in IP, but runs only
on the IPv4 subnet, while the IPv6 version runs on the link using only
link-local addressing.
IGRP, and EIGRP are directly encapsulated in IP.
EIGRP uses its own reliable transmission mechanism, while IGRP
assumed an unreliable transport.
Routing Information Protocol (RIP) runs over the User Datagram
Protocol (UDP).
Version 1 operates in broadcast mode, while version 2 uses multicast
addressing.
BGP runs over the Transmission Control Protocol (TCP).
1.7 Broadcast, multicast,
anycast
In broadcast routing, the network layer provides a
service of delivering a packet sent from a source node to all other
nodes in the network.
Multicast routing enables a single source node to
send a copy of a packet to a subset of the other network nodes.
IPv6 has introduced a new type of address, called an
anycast address, which allows a datagram to be
delivered to any one of a group of hosts.
This feature could be used, for example, to send an HTTP GET to the
nearest of a number of mirror sites that contain a given document
1.7.1 Broadcast
When a host sends a datagram with destination address
255.255.255.255, the message is delivered to all hosts on the same
sub-net.
How to broadcast?
Several possible mechanisms, with pros and cons:
Flooding:
when node receives broadcast packet, sends copy to all
neighbors
problems: cycles & broadcast storm
Controlled flooding:
node only broadcasts packet, if it hasn’t broadcast same packet
before
node keeps track of packet ids already broadacsted
or reverse path forwarding (RPF):
only forward packet, if it arrived on shortest path between node and
source
