IP Routing Types & Algorithms (IPRTA)

Routing algorithms are used to build and manage routing tables on devices.

There are 2 ways to build a routing table, namely:

Static Routing: This routing is built based on the administrator's definition.
Dynamic Routing: This algorithm can make the router device to be able to determine its routing path automatically, by exploring the network and exchanging routing information between routers. There are 3 categories of dynamic algorithms, namely; Distance Vector, Link State, Hybrid .

1. Static Routing

Static routing is a route entry done by an administrator to set the path of a data packet. Routing table entries can be done with a program on the device.

2. Distance Vector Routing

This routing uses the Bellman-Ford algorithm. Where each router on the network has information on which path is the shortest to contact the next segment. Then the routers will send the information to each other, and finally the shorter path will be more often chosen to be the path to the destination host.

The protocol that uses this algorithm is RIP.

3. Link State Routing

This routing uses link state technique, which means each router will collect information about interface, bandwidth, roundtrip and so on. Then between routers will exchange information, the most efficient value will be taken as a path and entered into the routing table. The exchanged state information is called Link State Advertisement (LSA).

By using the Shortest Path First (SPF) decision-making algorithm, the LSA information will be arranged in such a way as to form a routing path. An illustration of SPF can be seen in Figure 6.3.

Figure 6.3 Shortest Path First

Routing protocols that use algorithms include OSPF.

4. Hybrid Routing

Routing is a combination of Distance Vector and Link State routing. An example of the use of this algorithm is EIGRP.

Types of Dynamic Routing Algorithms

1. Distance Vector Routing Protocol

A distance vector protocol provides information about the number of hops to the destination network (the distance) and the direction in which a packet can reach the destination network (the vector). The distance vector algorithm, also known as the Bellman-Ford algorithm, enables routers to pass route updates to their neighbors at regularly scheduled intervals. Each neighbor then receives its own destination value and passes the routing information to its nearest neighbor. The result of this process is a table containing a collection of all distances/destinations to all destination networks.

Distance vector routing protocols, early dynamic routing protocols, improvements over static routing, but have some limitations, when the internetwork topology changes, distance vector routing protocols take several minutes to detect the changes and make adjustment corrections.

One advantage of distance vector routing protocols is simplicity. Distance vector routing protocols are easy to configure and maintain. They are suitable for small networks with low performance requirements.

Most distance vector routing protocols use hop count as the routing metric. A routing metric is a number associated with a route that is used to select the best routes for the IP routing table. A hop count is the number of routers a packet must pass through to reach its destination. How distance vector works.

fig.1
fig.1

Fig. Final distance vector routing tables

Figure 62. How Distance Vector Works

Assume the router is in a new state
Early routers only had information about networks directly connected to them.
In Figure 63. Routers Sending Information to Each Other, Routers Sending Information to Each Other routers will send each other the information they have.
RTA routers send data about the networks they are connected to directly.
RTB routers also send data to the networks connected to them directly.

Figure 63. Routers Sending Information to Each Other

Each router checks the data it receives, comparing it with each router's routing table.
If none have been entered, if they have, compare the number of hops.

Figure 64. Router Performs Routing Table Comparison

Types of distance vector routing protocols:

RIP (Routing Information Protocol)
BGP (Border Gateway Protocol).

1.1 Routing Information Protocol (RIP)

Known as the Bellman-Ford Algorithm which is the oldest algorithm that is known to be slow and causes routing loops. First introduced in 1969 and is the first routing algorithm on ARPANET.

RIP is a routing protocol with a distance vector algorithm, which calculates the number of hops (hop count) as a routing metric. The maximum number of hops allowed is 15 hops. Each RIP router exchanges routing information every 30 seconds, via UDP port 520. To avoid routing loops, the split horizon with poison reverse technique is used. RIP is the easiest routing protocol to configure.

Routing Loop is a condition where routers think they are reaching the same destination through neighboring routers. For example, router A thinks it is reaching network xxx through router B, while router B itself thinks it is reaching network xxx through router A, this can also happen between 3 routers.

To improve its performance, a split horizon is known, where the router does not need to send data that it has received from the path where it sent the data, for example, if the router sends routing via eth0, then the router will never send back data that it has received from the eth0 interface.

Meanwhile, to speed up the process, a trigger update is also known, so that if there is a change in routing information, the router does not need to wait for the normal interval time to send the change in routing information but as soon as possible.

RIP has 3 versions namely RIPv1, RIPv2, RIPng:

RIPv1 is defined in RFC 1058, which uses classful routing, does not use subnets. It does not support Variable Length Subnet Mask (VLSM).
RIPv2 came around 1994, improving the capabilities of Classless Inter-Domain Routing. Defined in RFC 2453.
RIPng is a RIP protocol for IPv6. It is defined in RFC 2080.

The best and most widely used distance vector routing protocol is Routing Information Protocol (RIP). RIP version 1 (RIP v1), which is now the first routing protocol model accepted as a standard for TCP/IP. RIP version 2 (RIP v2) provides authentication support, multicast announcing, and better support for network classification.

1.2 Border Gateway Protocol

BGP is a router for external networks. BGP is used to avoid routing loops on the internet network. The BGP standard uses RFC 1771 which contains BGP version 4.

Figure 65. BGP components

1). BGP Speaker: A router that supports BGP.

2.) BGP Neighbor (pair): A pair of BGP routers that exchange information with each other.

There are 2 types of neighbors:

Internal (IBGP) neighbor : a BGP pair that uses the same AS.
External (EBGP) neighbor : a BGP pair that uses different ASes.

3) BGP session: session of 2 BGPs that are currently connected

4) Traffic type:

Local : local traffic to the US
Transit: all traffic that is not local.

5) US Type :

Stub: the part of the AS that is connected to only 1 connection with the AS.
Multihomed: this section is connected to 2 or more AS, but does not forward transit traffic.

6) Transit: this section is connected to 2 or more AS, and forwards local and transit packets.

7) AS Number: 16 bit unique number

8) AS path: the path taken by routing with AS number

9) Routing Policy: rules that must be followed regarding how to forward packets.

10) Network Layer Reachability Information (NLRI): used to advertise routers.

11) Routes and Paths: routing table entries.

BGP neighbor, peer, makes a connection according to the manual configuration on the router device and creates a TCP path with port 179. BGP speaker will send 19 bytes of persist message to maintain connectivity (done every 60 seconds). When BGP runs in the AS system, it processes IBGP routing information until it reaches administrative distance 200. When BGP runs between AS systems, it will process EBGP routing information until it reaches administrative distance 20. BGP routers that process IBGP traffic are called transit routers. Routers that are on the outside of the AS system and use EBGP will exchange information with the ISP router.

The increasing number of networks will result in an increasing number of routing tables on the BGP router. To overcome this, route reflectors (RFC 2796) and Confederation (RFC 3065) can be used. Router reflectors will reduce the number of connections needed by the AS. With a router (or two routers for redundancy) can be used as a router reflector (router duplication), so that other routers can be used as peers. Confederation is used for large-scale AS networks, and can create shortcuts so that internal routing on the AS will be easy to manage. Confederation can be run simultaneously with router reflectors.

2. Link State Routing Protocol

This routing uses link state technique, which means each router will search for information about interface, bandwidth, roundtrip and so on. Then between routers will exchange information, the most efficient value will be taken as a path and entered into the routing table. The exchanged state information is called Link State Advertisement (LSA).

By using the Shortest Path First (SPF) decision-making algorithm, the LSA information will be arranged in such a way as to form a routing path.

Figure 66. Shortest Path First

Some limitations of link state routing protocols address distance vector routing protocols, for example link state routing protocols provide faster convergence than distance vector routing protocols. Convergence is the process by which routers update their routing tables after changes in the network topology -- changes that are redundant for all routers that need to know about them. Although link state routing protocols are more reliable and require less bandwidth than distance vector routing protocols, they are also more complex, more memory-intensive, and more CPU-heavy.

Each path has a metric, which indicates the cost, the lower the cost the better. Each router will create a tree of destination routers based on the existing costs, unlike distance vector routing protocols, which broadcast updates to all routers at regular intervals, link state routing protocols update only when the network link conditions change. When that happens, a notification in the form of a link condition announcement is sent across the network.

Figure 67. Link State Stage

Link-State Stages

Each router introduces itself, by sending a hello packet.
Each router will know its neighbors based on hello packets and their costs, entered into a database.
Each router sends its database to its neighbors in LSA packets.
A router that receives an LSA packet must forward it to its next neighbor.
LSA packets are entered into the database if their info is newer.
Initially, flooding occurs because each router, when there is a data update, will send it to the convergent, as in Figure 68. Flooding occurs.
Next, each router calculates the shortest distance to the other router using Shortest Path First, and a tree is formed.
It is possible to reach the same Router, between routers have different trees.

Figure 68. Floating occurs

2.1 Open Shortest Path First (OSPF)

The most widely known and widely used link state routing protocol. OSPF is an open standard developed by the Internet Engineering Task Force (IETF) as an alternative to RIP. OSPF compiles a complete topology database of the internetwork. The shortest path first (SPF) algorithm, also known as Dijkstra's algorithm, is used to calculate the least cost to reach a destination. Where RIP calculates the cost based only on the hop count, OSPF can calculate metrics such as link speed and reliability in addition to the hop count. If there is a topology change, Routing updates occur with a flooded system.

Unlike RIP, OSPF can support a network with a diameter of 65,535 (assuming each link is assigned a single cost). OSPF broadcasts multicast frames, reducing CPU usage on the LAN. OSPF hierarchically divides the network into areas, reducing router memory and CPU usage.

Routers in the same broadcast domain will perform adjacencies to detect each other. Detection is done by listening to "Hello Packets". This is called 2 way state. OSPF routers send "Hello Packets" in unicast and multicast ways. Multicast addresses 224.0.0.5 and 224.0.0.6 are used by OSPF, so OSPF does not use TCP or UDP but IP protocol 89.

OSPF network example

OSPF routing example through Zebra

Example using IProute

Understanding Dynamic Routing

With the growing network, a protocol is needed that is able to create routes for routing tables. Routing is a function that is responsible for carrying data through a set of networks by choosing the best path for data to pass through. And this cannot be done properly if an admin is used to update the routing table. In order for the router to forward data, the computer on the network must assign the router to forward data, the assignment is done by setting the default gateway computer to the router, if we do not set the default gateway then it is certain that the LAN cannot connect to other networks. The problem in building the routing table can be overcome by using dynamic routing.

Dynamic Routing is one type of routing, where the router learns and updates the routing table if there is a change. Learning is done by communicating between routers with certain protocols. Algorithms used in dynamic routing include Distance vector routing protocols, Link state routing protocols, Hybrid.

This paper discusses the Dynamic routing protocol used in creating a routing table on a network. Starting from the algorithm used in dynamic routing to its configuration.

1. Introduction

The main function of the network layer is addressing and routing. Routing is a function that is responsible for carrying data through a set of networks by selecting the best path for the data to pass through.

Routing tasks will be carried out by a network device called a Router. A router is a network computer that is tasked or functioned to connect two or more networks. Types of routers include: computers that we function as Routers or special equipment designed as Routers. The router's task is to forward data (IP Forward Function must be activated) using a routing protocol (Routing Algorithm). Data is regulated by the Routed Protocol.

A router is a general purpose computer (for a wider purpose) with two or more network interfaces (NIC Cards) in it that function to connect 2 or more networks, so that it can forward packets from one network to another. For small networks, the interface is the NIC Card, so the router has 2 or more NICs that can connect to other networks. For small LANs connected to the internet, one of the interfaces is the NIC card, and the other interface is any network hardware such as a modem for a leased line or ISDN or ADSL internet connection used.

In order for the router to forward data, the computers on the network must assign the router to forward data. This assignment is done by setting the computer as the default gateway to the router. If we do not set the default gateway, it is certain that the LAN will not be able to connect to other networks.

2. How to Build a Routing Table

Static Routing. Built based on the definition of the administrator, the administrator must be careful, if only one wrong routing table the network will not be connected.
Default Routing. Sending packets to a network that is not in the routing table to the next Router. This happens if the Router only has one outgoing port.
Dynamic Routing. Automatically the router routes its path, by exchanging information between routers using certain protocols.

3. Dynamic Routing

Dynamic routing is one type of routing, where the router learns and updates the routing table if there is a change. Learning is done by communicating between routers with certain protocols.

The concept of dynamic routing method has two parts:

Routing protocols are used between neighboring routers to provide each other with information about their networks.
routing algorithm that determines the choice through that network.

Protocols depend on the method used to share external information, where algorithms are the methods used to process internal information. The routing table in a dynamic router is updated automatically based on changes in routing information with other routers. Algorithms used in dynamic routing include:

Distance vector routing protocols
Link state routing protocols
Hybrid.

To understand how this protocol works, you can choose the type of dynamic routing that is best needed by the network. The algorithm above has a protocol that functions as software that exchanges routing information to form a routing table, periodically updates the routing table, determines the best route.

The advantage of dynamic routing when compared to others is because the network is not a static system, meaning that the network is dynamic, which means it changes - this is in accordance with dynamic routing which will automatically adapt to network developments, network developments in general are very rapid. Unlike static routing, where route changes are slow, but in dynamic routing, this is different because there is a periodic update of network conditions and a response to changes in the link that occur.

IPv6 Routing Protocol

The routing protocols used in IPv6 are BGP4+ for external routing and OSPFv6, RIPng for internal routing.

1. BGP4+

Border Gateway Protocol is a routing protocol that uses autonomous systems. The main function of BGP is to exchange network connectivity information between BGP systems. This connectivity information includes a list of Autonomous Systems (ASs). This information is used to create a routing list so that a connection occurs.

BGP4 is capable of doing an advertisement and IP-prefix and eliminating limitations on network class. BGP uses a Hop-by-Hop pattern which means it only uses the next path registered in the Autonomous System.

BGP uses TCP as the transport medium. BGP uses port 179 for BGP connections. BGP supports CIDR.

Figure 2. BGP Model

BGP is able to learn internet paths through internal or external BGP and can choose the best path and include it in ip forwarding. BGP can be used on dual or multi-homed, provided it has an AS value. BGP cannot be used on single-homed.

Types of BGP:

OPEN, the type of message received when a BGP connection is established.
UPDATE, a message type sent to send routing information between BGP.
KEEPALIVE, a message type sent to find out whether a BGP pair is still alive.
NOTIFICATION, the type of message sent when an error occurs.

1.1. BGP Attributes

AS_path, is the path that is passed and recorded in the BGP route data, and can detect loops. Next_Hop, is the next path that will be passed in BGP routing, usually a local network in eBGP. In addition, it can be obtained from iBGP. Local Preference, a marker for AS BGP local Multi-Exit Discriminator (MED), is non-transitive and is used if you have more than 1 eBGP. Community, is a group of BGPs in one AS. The comparison of BGP-4 between those used for IPv4 and IPv6 is the ability of BGP to recognize the scope of IPv6, namely global, site-local, link-local. If IPv6 still uses IPv4 as transport, then the peer addresses on other BGPs must be included in the configuration.

2. RIPng

Routing Information Protocol Next Generation is a routing protocol based on the RIP routing protocol in IPv4 that already supports IPv6. RIPng is used for internal routing protocols and uses the UDP protocol as transport. RIPng uses port 521 as communication between RIPng.

The method used by RIPng is distance vector, namely:

Local network distance is calculated as 0
Then look for neighbors around and calculate the distance and cost.
Compared to distance and cost between neighbors.
Calculations are carried out continuously.
Using the Ballman-Ford algorithm.

Figure 4. RIP Header Format

The command in the RIPng Header contains:

Request, requesting a list of routing tables on another RIPng
Response, replies to requests from other RIPng and provides a routing list.

This RIPng protocol has several weaknesses

Only up to 15 HOPs
Slow in processing routing, due to continuous checking
Classy in nature.

The difference between RIP on IPv4 (RIPv2) and IPv6 (RIPng) is the UDP port where IPv4 uses port 520 while IPv6 uses port 521 as the transport media. RIPng only has 2 commands, namely response and request, in contrast to RIPv2 which has many commands and many are unused and some are discarded in RIPng such as authentication. Changes that occur from RIPv2 to RIPng include, the routing size is no longer limited, the IPv4 subnet is replaced with the IPv6 prefix, the next-hop is removed but its usefulness is not removed, authentication is removed, but the ability of only up to 15 hops is still the same.

3. OSPFv3

Open Shortest Path First is a routing protocol used in IPv6. OSPF is based on Link-state and not based on distance. Each node of OSPF collects state data and collects it in Link State Packet.

LSP is broadcasted on each node to reach the entire network. After the entire network has a "map" of the results of the LSP information and is used as the basis for the OSPF link-state. Then each OSPF will search using the SPF (Shortest Path First) method to find a more efficient distance.

The resulting routing table is based on the LSP information obtained so that OSPF provides LSP information via flood, because OSPF already has the ability to select the same LSP information, this flood does not result in exhaustion.

OSPF uses TCP protocol instead of UDP, supports VLSM (Variable Length Subnet Mask).

OSPF uses the Shortest Path First (SPF) algorithm by Dijkstra, namely:

Assuming there is already a previous table data. The required data includes PATH (ID, path cost, forwarding direction) TENTATIVE (ID, path cost, forwarding direction), Forwarding database.
Put local as the root of the tree with ID,0,0 in PATH
Find link N and put it in PATH. Calculate the distance between Root-N and NM, if M is not yet in PATH or TENTATIVE, if the value is better put it in TENTATIVE.
If TENTATIVE is empty, cancel. Else, enter the TENTATIVE value into PATH.

Table 5. OSPF Header Format

OSPF Description:

Version, 8 bits, filled with the OSPF version. Type, 8 bits, filled with the OSPF type code, namely:

Hello, to find out if there is an OSPF partner
Database Description, sends a description of OSPF
Link State Request, requests data from an OSPF partner.
Link State Update, updates table data on OSPF

Link State Acknowledgement, sending error message

-   Length, 16 bit, panjang header dan data dari OSPF
-   Router ID, 32 bit, Router ID dari source paket Area ID, 32 bit, Area dari paket ini.
-   Checksum, 16 bit
-   AuType, 16 bit, model autentifikasi dari OSPF
-   Authentication, 64 bit, misal tanpa autenticasi, simple password, cryptographic password.

Description for OSPFv3:

Version, 8 bit, set to 3
Checksum, 16 bit, CRC
Instance ID, 8 bit
Reserves, 8 bits set to 0.

3.1. Comparison between Link State and Distance Vector

Faster conversion than Distance Vector
Easy in the form of Network Topology
Easy in terms of Routing
Can have complex routing tables.

3.2. Differences Between OSPF IPv4 and OSPF IPv6

Communication using link-state does not use subnets.
Eliminate semantic addresses.
Using IPv6 scopes, namely: link-local scope, area-scope, AS scope.
Supports multiple OSPF on the same link.
Using link-local addresses.
Remove authentication.
Package format changes.

IPv6 Infrastructure Example

IPv4, the foundation of the Internet, has almost reached the end of its capabilities, and IPv6, a new protocol, has been designed to replace IPv4. The main motivation for replacing IPv4 is due to the limitations of its address length of only 32 bits and its inability to support the need for secure communication, flexible routing, and data traffic management. The advantages of IPv6 compared to IPv4 include automatic stateless and statefull settings. Then, the basis for migration / change from IPv4 to IPv6 includes address expansion capacity, simplification of header formats, options and extension headers, packet flow labeling capabilities, and authentication and privacy capabilities. To overcome the obstacles of differences between IPv4 and IPv6 and to ensure the implementation of communication between IPv4 users and IPv6 users, a Hosts - dual stack and Networks - Tunneling method was created on network hardware, such as routers and servers.

Figure 3. IPv6 infrastructure

Figure 4. IPv6 infrastructure

Question

Briefly explain the meaning of firewall and its simple configuration!
Mention and explain the types of firewalls!
What are the steps to build a firewall in a simple way?
What is the background to using NAT? And what are the advantages of using NAT?
Name the components that a NAT has!