Abstract:
Computing shortest paths in graphs is one of the most fundamental and well-studied
problems in combinatorial optimization. Numerous real-world applications have stimulated
research investigations for more than 50 years. Finding routes in road and
public transportation networks is a classical application motivating the study of the
shortest path problem. Nowadays shortest paths are play important role in by routing
schemes for computer networks. One of the high demand examples in last decades
was routing mechanism of applications with high load inside load balancer.
In a client-server model, the client and server interact with each other to exchange
information and perform different tasks. Modern high-load applications usually have
hundreds and thousands of servers. In order to properly navigate client request to
certain server developers are using load-balancing systems. A load balancing system
is a type of system that distributes workloads across multiple servers or computing
resources to optimize resource utilization, increase availability, and improve the overall
performance of the system. The goal of load balancing is to ensure that no single
server or resource is overwhelmed by the workload, while ensuring that the resources
are used efficiently and effectively. In a load balancing system, a central component,
called a load balancer, is responsible for routing incoming requests from clients
to the appropriate server or resource. The load balancer distributes the requests
across multiple servers or resources based on different factors, such as server capacity,
server response time, server availability, and server load. By distributing the requests
across multiple servers, load balancing can help to reduce the response time, increase
throughput, and improve the overall performance of the system. Load balancers are
networking devices that distribute incoming network traffic across multiple servers in
a cluster. When a client sends a request to a load balancer, the load balancer uses a
variety of algorithms to decide which server in the cluster should handle the request.
Once the decision is made, the load balancer redirects the incoming request to the
chosen server. They can be static algorithms or custom ones based on some server
characteristics. And as a custom algorithms we can use shortest path algorithms. In
this work we will try to find most optimal shortest path algorithm that will work
mostly for basic use cases.