9. LP Modelling: Bandwidth Allocation

So, suppose we have a small communication network involving three users. So, the users are capital A, capital B and capital C, and each of them is connected through some switches, which we call a, b and c. So, we have a network which this in an internet network which connect these three users and our requirement is to ensure that each pair of users A to B, B to C and A to C gets at least two mega bits per second of connectivity from between that pair of users.

In this chunk, we introduce a simple communication network comprising three users, A, B, and C. Each of these users is connected via switches labeled a, b, and c. The goal of the network is to provide adequate data flow, specifically at least 2 Mbps, between each pair of users (A to B, B to C, and A to C). This sets the stage for understanding how bandwidth must be allocated to meet user needs.

Imagine you are in a small shared office with three colleagues who need to communicate using the internet. You need to ensure that they can all send messages to each other quickly enough, which is like ensuring they have enough lanes on a road for traffic to flow smoothly between them.

Now, notice that from A to B, there are two ways I can sent packets. I can sent that directly via A and B or I can sent them indirectly, I have small seek. So, it turns out, it does not really matter from the viewpoint we uses whether this 2 Mbps bandwidth comes from the shorter red route and a longer green route. So our aim is to combine the capacity of the red and the green for each pair.

This chunk discusses the flexibility in choosing routes for data packets. Between users A and B, data can be sent directly or indirectly, implying there are multiple pathways for transferring data. The key takeaway is that as long as the total bandwidth from both routes meets the minimum requirement of 2 Mbps, the specific routes chosen (shorter or longer) do not matter for achieving connectivity.

Think of this like driving to a friend's house. You can take a direct route that's quicker or a longer scenic route that takes more time but is enjoyable. In both cases, you arrive at your friend's house, similar to how data can flow between users.

On the other side, we earn some money from this customer which is not uniform. So, for the A, B link, we get 300 rupees for mega bit Mbps per month, but from B to C we get only 200, but from A to C we get 400. So, now, we have to allocate a minimum of 2 mega bits. But customers are willing to take as much as we can give them subject to that minimum and we get a certain amount of revenue depending on how we utilizes the capacity.

This section highlights the economic aspect of bandwidth allocation. Each connection (A to B, B to C, A to C) generates different revenues per megabit transported. Specifically, A to B earns 300 rupees, B to C 200 rupees, and A to C 400 rupees. The challenge is to allocate bandwidth effectively while ensuring the minimum requirement of 2 Mbps per connection is satisfied, which plays a crucial role in maximizing the total revenue generated from these connections.

Imagine running a pizza delivery business where each type of pizza (A to B, B to C, A to C) generates different profits. You need to meet the demand of at least a few pizzas to each neighborhood (2 Mbps), and your goal is to figure out how many pizzas to deliver to maximize your overall profit.

So, in this case, what are the variables that we are going to use? So, recall that we said that every connection has two routes. So, we have A to B coming where the short route and we have A to B coming by either long route. So, what we use is the variable x, from A to B to denote that quantity that is showing on the red route and similarly, y from A to B to denote the quantity, it is flowing on the green route.

In this chunk, we define the variables used to represent the bandwidth allocation in the network. Each route has a variable: x represents the direct or shorter route while y corresponds to the indirect or longer route. This allows us to express the flow of data mathematically, helping us formulate the linear programming model.

Think of x and y like two different delivery trucks you can send to transport packages between two stores. One truck takes a direct route (x) while the other uses a longer, more scenic route (y). By knowing how many packages each truck can carry, you can efficiently plan your delivery routes.

Now, these variables are constrained by the capacities of links. ... So, all these four routes put together will add up to whatever capacities flowing through this link and this link has capacity 10, so x A B plus y A b plus x B C plus y B C has to be at most 10.

This part introduces constraints related to the capacity of the links in the network. Each link can handle a maximum amount of bandwidth (e.g., 10 Mbps). The sum of the bandwidth on all routes that utilize a particular link cannot exceed its capacity. This limitation is crucial in ensuring that the network operates efficiently and does not exceed its operational capabilities.

Consider a water pipe. The pipe can only carry a certain amount of water (its capacity). If you try to send too much water through it at once, it will overflow. Similarly, in our network, we must ensure we don’t exceed the maximum bandwidth the links can handle.

What are the objective functions? The objective function is the revenue that we realize. ... So, multiply these revenues with the corresponding variables and add it up; this is our total revenue, and we want to maximize this revenue.

Here we discuss the formulation of the objective function for the linear programming model. The goal is to maximize revenue generated from bandwidth allocations. By combining the revenue per Mbps from each link with the corresponding variables, we can determine the total revenue and establish a method for maximizing it under the given constraints.

Imagine you're running a lemonade stand where you earn different amounts for each cup sold throughout the day. You want to figure out how to produce the right amount of lemonade (bandwidth) to maximize your profit when selling to each customer.

There is however, another problem which is the way we are actually set up the linear program... we would like the number of variables we get to be small say polynomial in the input problem.

While setting up the linear programming model for bandwidth allocation looks straightforward, the complexity can increase significantly as the number of variables grows. The linear programming model may become difficult to manage if the number of paths increases exponentially. Therefore, the goal is to develop a model that efficiently captures network flows without requiring an overwhelming number of variables.

Picture organizing a large event. If you have too many tasks to manage (like booking venues, food, invites), you might get overwhelmed, making it hard to keep everything running smoothly. You want a manageable list of tasks to ensure a successful event, just like we want a manageable number of variables to maintain an efficient linear programming model.

--