Network and Network Security Summary CHoogteijling
5 The Network Layer: Control Plane
5.1 Introduction
The two ways of computing, maintaining and installing flow tables:
• Per-router control. In each router a forwarding and routing function is contained and
it communicates with other routers to compute the values for its forwarding table.
OSPF and BGP are based on this.
• Logically centralized control. A logically centralized controller computes and distributes
the forwarding tables to each router. It allows traditional IP forwarding and other
functions, such as load sharing, firewalling and NAT.
5.2 Routing Algorithms
Routing algorithms determine paths from senders to receivers through the network of routers.
The path has to have the least cost but also should follow policy issues.
A graph (G = (N, E)) is a set of nodes (N ) and a collection of edges (E), where each edge
is a pair of nodes (from N ). The nodes are routers and the edges the physical links between
the routers. Each edge has a cost (c(x, y)) and if the pair does not belong to the graph the
cost is infinite. A node is a neighbor of another node if its pair belongs to the graph.
A path is a sequence of nodes such that each pair belongs to the edges of the graph
(x1 , x2 , . . . , xn ). The least-cost path is the path between the nodes with the lowest cost.
The shortest-path is the path with the smallest number of links between source and desti-
nation. This is also the least-cost path if all edges have the same cost.
Routing algorithms can be classified as centralized or decentralized algorithms:
• A centralized routing algorithm uses a link-state (LS) algorithm to compute the least-
cost path. It performs a calculation based on global knowledge of the network and all
nodes and edges in it.
• A decentralized routing algorithm uses a distance-vector (DV) algorithm to compute
the least-cost path. No node has complete information about the costs of all the
network links, so they calculate the cost to each destination through a process of
exchanging information. Each node maintains a vector of estimates of the costs to all
other nodes in the network.
Routing algorithms can also be classified as static or dynamic algorithms:
• In a static routing algorithm the routes change very slowly over time, often as a result
of human intervention.
• Dynamic routing algorithms change the routing paths as the network traffic loads or
topology change. They are more responsive to network changes but are also more
susceptible to problems (routing loops, route oscillation).
Routing algorithms can also be classified as load-sensitive or load-insensitive algorithms:
• In a load-sensitive algorithm, link costs vary dynamically to reflect the current level
of congestion. If a cost is high the path will go around this edge.
• A load-insensitive algorithm does not use congestion as a cost, because it does not
explicitly reflect its current level of congestion.
, page 41 of 83
,Network and Network Security Summary CHoogteijling
The Link-State (LS) Routing Algorithm
In a link-state algorithm, the network topology and all link costs are known and available
as input to the LS algorithm. This is accomplished by each node broadcasting link-state
packets to all other nodes in the network. Each node can then run the LS algorithm.
Dijkstra’s algorithm computes the least-cost path from one node to all other nodes in the
network. It is iterative and has the property that after the kth iteration of the algorithm,
the leas-cost paths are known to k destination nodes. Among the least-cost paths to all
destination nodes, these k paths will have the k smallest costs. The worst case complexity
is O(n2 ).
Route oscillation is flipping between multiple choices, while it is not necessary or unproduc-
tive. This can happen in any LS routing algorithm. A way to avoid this is for each router
to randomize the time it sends out a link advertisement.
The Distance-Vector (DV) Algorithm
The distance-vector (DV) algorithm is iterative, asynchronous and distributed.
• Distributed: each node receives some information from its directly attached neighbors,
performs a calculation, and then distributes the results back.
• Iterative: this process continues on until no more information is exchanged between
neighbors, it is self-terminating.
• Asynchronous: all the nodes do not operate one after the other.
Each node computes its own distance vector and updates its routing table when they receive
information from their neighbors, then they send information to their neighbors. The nodes
update their routing table by computing the least-cost path with the Bellman-Ford equation.
Let dx (y) be the cost of the least-cost path from node x to node y. Then the least costs are
related by the Bellman-Ford equation: dx (y) = minv {c(x, v) + dv (y)}.
DV-like algorithms are used in many routing protocols in practice: RIP, BGP, ISO, IDRP,
Novell IPX and the original ARPAnet.
Distance-Vector Algorithm: Link-Cost Changes and Link Failure
When a link-cost decreases the information is send through the network quickly. When a
link-cost increases, the information is send through the network very slowly and packets can
get stuck in a routing loop. A routing loop sends a packet back and forth between two nodes
because they both have information that the other node is the fastest way to the destination.
This is the count-to-infinity problem.
Distance-Vector Algorithm: Adding Poisoned Reverse
Poisoned reverse is a technique in which a node tells its neighbor that one of the nodes is
no longer connected, by setting the least-cost path to infinite. The neighbor will not use the
edge but any other node still can. This does not solve the count-to-infinity problem.
A Comparison of LS and DV Routing Algorithms
A comparison of LS and DV algorithms attributes:
, page 42 of 83
, Network and Network Security Summary CHoogteijling
• Message complexity. LS always broadcasts (O(| N |2 )) messages whenever a link cost
changes. DV only sends messages to its direct neighbors.
• Speed of convergence. Both LS and DV converge slowly and DV has the count-to-
infinity problem.
• Robustness. LS nodes compute their least-cost paths separated, this gives a degree of
robustness. For DV an incorrect calculation can be spread through the entire network.
5.3 Intra-AS Routing in the Internet: OSPF
The model with a homogenous set of routers, all executing the same routing algorithm
is simplistic because of scale, overhead, and administrative autonomy. This can also be
achieved with autonomous systems.
An autonomous system (AS) is a group of routers that are under the same administrative
control. An AS is identified by its globally unique autonomous system number (ASN). The
intra-autonomous system routing protocol of an AS is the routing algorithm running in each
router.
Open Shortest Path First (OSPF)
OSPF is a link-state protocol that uses flooding of link-state information and a Dijkstra’s
least-cost path algorithm. Each router constructs a complete topological map of the au-
tonomous system and locally runs Dijkstra’s shortest-path algorithm to determine a shortest-
path tree to all subnets.
Individual link costs are configured by the network administrator. Minimum-hop routing
is achieved if all link weights are 1. If the link weights are inversely proportional to link
capacity, traffic on low-bandwidth links is discouraged.
A router broadcasts routing information to all other routers in the AS. It broadcasts when
there is a change in a link’s state and periodically, even if nothing has changed. This adds
to its robustness. The messages are send directly by IP with an upper-layer protocol of 89
for OSPF So the OSPF protocol must itself implement functionality for reliable message
transfer and link-state broadcast.
Advances of OSPF:
• Security: simple authentication send a password in plain text, MD5 uses authentication
on shared hashed keys.
• Multiple same-cost paths: when multiple paths to a destination have the same cost,
they all can be used.
• Integrated support for unicast and multicast routing: multicast OSPF (MOSPF) pro-
vides an extension to OSPF for multicast routing. It adds a new type of link-state
advertisements.
• Support for hierarchy within a single AS: an OSPF AS can be configured hierarchically
into areas. An area has border routers to pass packets to other areas. Exactly one
area is the backbone area, which has all the border routers in the AS.
, page 43 of 83
5 The Network Layer: Control Plane
5.1 Introduction
The two ways of computing, maintaining and installing flow tables:
• Per-router control. In each router a forwarding and routing function is contained and
it communicates with other routers to compute the values for its forwarding table.
OSPF and BGP are based on this.
• Logically centralized control. A logically centralized controller computes and distributes
the forwarding tables to each router. It allows traditional IP forwarding and other
functions, such as load sharing, firewalling and NAT.
5.2 Routing Algorithms
Routing algorithms determine paths from senders to receivers through the network of routers.
The path has to have the least cost but also should follow policy issues.
A graph (G = (N, E)) is a set of nodes (N ) and a collection of edges (E), where each edge
is a pair of nodes (from N ). The nodes are routers and the edges the physical links between
the routers. Each edge has a cost (c(x, y)) and if the pair does not belong to the graph the
cost is infinite. A node is a neighbor of another node if its pair belongs to the graph.
A path is a sequence of nodes such that each pair belongs to the edges of the graph
(x1 , x2 , . . . , xn ). The least-cost path is the path between the nodes with the lowest cost.
The shortest-path is the path with the smallest number of links between source and desti-
nation. This is also the least-cost path if all edges have the same cost.
Routing algorithms can be classified as centralized or decentralized algorithms:
• A centralized routing algorithm uses a link-state (LS) algorithm to compute the least-
cost path. It performs a calculation based on global knowledge of the network and all
nodes and edges in it.
• A decentralized routing algorithm uses a distance-vector (DV) algorithm to compute
the least-cost path. No node has complete information about the costs of all the
network links, so they calculate the cost to each destination through a process of
exchanging information. Each node maintains a vector of estimates of the costs to all
other nodes in the network.
Routing algorithms can also be classified as static or dynamic algorithms:
• In a static routing algorithm the routes change very slowly over time, often as a result
of human intervention.
• Dynamic routing algorithms change the routing paths as the network traffic loads or
topology change. They are more responsive to network changes but are also more
susceptible to problems (routing loops, route oscillation).
Routing algorithms can also be classified as load-sensitive or load-insensitive algorithms:
• In a load-sensitive algorithm, link costs vary dynamically to reflect the current level
of congestion. If a cost is high the path will go around this edge.
• A load-insensitive algorithm does not use congestion as a cost, because it does not
explicitly reflect its current level of congestion.
, page 41 of 83
,Network and Network Security Summary CHoogteijling
The Link-State (LS) Routing Algorithm
In a link-state algorithm, the network topology and all link costs are known and available
as input to the LS algorithm. This is accomplished by each node broadcasting link-state
packets to all other nodes in the network. Each node can then run the LS algorithm.
Dijkstra’s algorithm computes the least-cost path from one node to all other nodes in the
network. It is iterative and has the property that after the kth iteration of the algorithm,
the leas-cost paths are known to k destination nodes. Among the least-cost paths to all
destination nodes, these k paths will have the k smallest costs. The worst case complexity
is O(n2 ).
Route oscillation is flipping between multiple choices, while it is not necessary or unproduc-
tive. This can happen in any LS routing algorithm. A way to avoid this is for each router
to randomize the time it sends out a link advertisement.
The Distance-Vector (DV) Algorithm
The distance-vector (DV) algorithm is iterative, asynchronous and distributed.
• Distributed: each node receives some information from its directly attached neighbors,
performs a calculation, and then distributes the results back.
• Iterative: this process continues on until no more information is exchanged between
neighbors, it is self-terminating.
• Asynchronous: all the nodes do not operate one after the other.
Each node computes its own distance vector and updates its routing table when they receive
information from their neighbors, then they send information to their neighbors. The nodes
update their routing table by computing the least-cost path with the Bellman-Ford equation.
Let dx (y) be the cost of the least-cost path from node x to node y. Then the least costs are
related by the Bellman-Ford equation: dx (y) = minv {c(x, v) + dv (y)}.
DV-like algorithms are used in many routing protocols in practice: RIP, BGP, ISO, IDRP,
Novell IPX and the original ARPAnet.
Distance-Vector Algorithm: Link-Cost Changes and Link Failure
When a link-cost decreases the information is send through the network quickly. When a
link-cost increases, the information is send through the network very slowly and packets can
get stuck in a routing loop. A routing loop sends a packet back and forth between two nodes
because they both have information that the other node is the fastest way to the destination.
This is the count-to-infinity problem.
Distance-Vector Algorithm: Adding Poisoned Reverse
Poisoned reverse is a technique in which a node tells its neighbor that one of the nodes is
no longer connected, by setting the least-cost path to infinite. The neighbor will not use the
edge but any other node still can. This does not solve the count-to-infinity problem.
A Comparison of LS and DV Routing Algorithms
A comparison of LS and DV algorithms attributes:
, page 42 of 83
, Network and Network Security Summary CHoogteijling
• Message complexity. LS always broadcasts (O(| N |2 )) messages whenever a link cost
changes. DV only sends messages to its direct neighbors.
• Speed of convergence. Both LS and DV converge slowly and DV has the count-to-
infinity problem.
• Robustness. LS nodes compute their least-cost paths separated, this gives a degree of
robustness. For DV an incorrect calculation can be spread through the entire network.
5.3 Intra-AS Routing in the Internet: OSPF
The model with a homogenous set of routers, all executing the same routing algorithm
is simplistic because of scale, overhead, and administrative autonomy. This can also be
achieved with autonomous systems.
An autonomous system (AS) is a group of routers that are under the same administrative
control. An AS is identified by its globally unique autonomous system number (ASN). The
intra-autonomous system routing protocol of an AS is the routing algorithm running in each
router.
Open Shortest Path First (OSPF)
OSPF is a link-state protocol that uses flooding of link-state information and a Dijkstra’s
least-cost path algorithm. Each router constructs a complete topological map of the au-
tonomous system and locally runs Dijkstra’s shortest-path algorithm to determine a shortest-
path tree to all subnets.
Individual link costs are configured by the network administrator. Minimum-hop routing
is achieved if all link weights are 1. If the link weights are inversely proportional to link
capacity, traffic on low-bandwidth links is discouraged.
A router broadcasts routing information to all other routers in the AS. It broadcasts when
there is a change in a link’s state and periodically, even if nothing has changed. This adds
to its robustness. The messages are send directly by IP with an upper-layer protocol of 89
for OSPF So the OSPF protocol must itself implement functionality for reliable message
transfer and link-state broadcast.
Advances of OSPF:
• Security: simple authentication send a password in plain text, MD5 uses authentication
on shared hashed keys.
• Multiple same-cost paths: when multiple paths to a destination have the same cost,
they all can be used.
• Integrated support for unicast and multicast routing: multicast OSPF (MOSPF) pro-
vides an extension to OSPF for multicast routing. It adds a new type of link-state
advertisements.
• Support for hierarchy within a single AS: an OSPF AS can be configured hierarchically
into areas. An area has border routers to pass packets to other areas. Exactly one
area is the backbone area, which has all the border routers in the AS.
, page 43 of 83
