CSE 331 Project

Details on the problems for the coding project. See the coding page for more details on the coding submissions, the reflections page for details on submitting the reflection problems and the survey page for details on submitting the survey.

Acknowledgment

The development of the project was supported by a Mozilla Responsible Computer Science award . The support is gratefully acknowledged.

Some Suggestions and Warnings

While this coding parts of the project is somewhat similar to Question 3s on the homework, there are some crucial differences and we wanted to highlight few things for y'all upfront:

Form groups of size EXACTLY $3$

This is a group project (unlike Q3s on the HWs that had to be done individually) and you can work in groups of size exactly 3. The submissions will be on Autolab and everyone in the group will get the same grade.

Groups should agree on one programming language

While the submission for the coding problems in this project can be done in any of C++,Java and Python like in Question 3s on the homework, we highly recommend that the group agrees on one programming language for the group. This will make it much easier for your group to make progress and collaborate.

The same group for ALL problems

You are expected to work in the same group for ALL problems in the coding project. Not doing so will be considered to be an academic integrity violation. We will use the groups y'all register on Autolab as part of your Autolab Project Group Registration submission for your project submissions.

There is ONE exception to the above rule: It is OK if the group becomes smaller (e.g. if a group member resigns) but in that case another student cannot be added to group. If you need clarification on this, please get in touch with Atri.

There are no optimal algorithms known!

Other than the first problem, we do not know of optimal algorithms to solve the rest of the problems and we suspect that doing so is not possible (definitely not within a semester). Note that this is unlike the HW Q3s where your code is supposed to always output the optimal/correct solution: i.e. you will have to think of algorithms where you might not be able to prove any guarantee on how good your output is.

Start early!

There is a reason we are giving y'all about two months to do this project. If your group starts even the week before the project is due, your group will be in trouble especially beyond the first problem. Also for most problems you will have to think of algorithms beyond what we cover in class, so the more time your spend on this, the better.

What algorithms techniques will be relevant?

Our solutions only use algorithmic techniques (plus some heuristics) that we will cover in class. However, it is entirely possible that other algorithmic techniques might be useful. One such technique that we will not cover in class is that of network flows (Chapter 7 in the textbook). However, again to emphasize since we have not used any concepts from that chapter in our solutions, we cannot speak to the efficacy of such techniques for this project. In other words, if your group decides to use network flow in your submission and it does not work well, then that is on your group.

Optimizing the runtime of your code is NOT the main objective

Unlike the HW Q3s, there will be no timeouts for individual inputs (though there will be one overall per submission). This is because unlike the HW Q3s, the main goal in this coding project submissions will be to generate as much "revenue" as possible (read on for more details on this)-- optimizing the runtime would/should be a secondary object but again there is an overall timeout so really inefficient implementations (and definitely not polynomial runtime algorithms) will not make the cut.

Use the Notation Table

The project description is a bit notation heavy. If you start losing track, here is the notation page (opens in a new window) that might be useful.

Coding, Reflection and Survey are on different pages

The details on coding, reflection problems and the survey are on different pages.

Background

Today reliable internet service is not a luxury, it is a necessity . In February 2017, a lawsuit was filed by New York states Attorney General Eric Schneiderman against Spectrum , which is a telecommunications company and also the largest provider of residential internet services in New York state. See e.g. the following from the AG's summons and complaint page 6 and point 2:

....Spectrum-TWC is the largest provider of residential Internet services in New York State. It provides Internet service to approximately 2.5 million New York households and earns well over a billion dollars in revenue annually from selling Internet services in New York.

Spectrum was accused of fraudulently misleading its Internet services customers by promising internet speeds that it knew it could not provide. Spectrum provided its customers with old generation modems and routers that it knew were incapable of achieving the promised internet speeds. Moreover, they are also accused of capping the bandwidth of routers in order to cut down on expenses and maximize their profit. There were more allegations against Spectrum. Here is the official lawsuit complaint against Spectrum with all the allegations.

Click here to see a summary of the allegations

Promised internet speeds differed from actual internet speeds, Spectrum made false advertisements and repeatedly assured its customers that they could achieve the same results with wireless as with a wired connection (even though wireless connection has other real world limitations).
Leased out older models of routers that were incapable of achieving the promised speeds (D1 and D2 as opposed to D3) due to “budget constraints” (maximizing profit).
Charged customers based on the prices advertised for the higher speed plans (the motive for said advertisement was to prevent subscribers from switching ISPs).
Promised to upgrade the routers without additional charges when tech improved but didn’t despite complaints from customers about the slow internet speed.
Even the current generation routers did not deliver the speed they had promised, since too many subscribers were grouped into the same service group (less bandwidth available per subscriber) and the number of channels did not increase (which could have increased the bandwidth). Only made modifications when the situation was dire. This led to an abysmal performance during peak hours.
Deceived the FCC by benchmarking speed during non-peak hours (and hence overestimating performance).
Changed modems for the FCC panelists doing the benchmarking but not for customers. The FCC results, as a result, painted them in a better light.
Did not invest in additional ports (cost per Gbps) to content providers which could have decreased latency/buffering/downtimes despite promising the opposite to consumers. In fact, leveraged their access to subscribers by extracting fees from content providers and delivering nothing in return, throttled the rate of content delivery in the absence of payments.
Started charging a monthly leasing fee for the same modems for which there had previously been no charge.
Customers were allowed to upgrade their modems to D3 but were subjected to long call hold times, the notice that was sent to customers conveniently left out the fact that their current modems were a bottleneck, there was a fee to install the modem, they had to return the D2 modem or pay an unreturned equipment fee in order to upgrade to D3 modems.
Programmed D2 routers to cap speeds at 20 Mbps but did not switch the pricing tier to a lower one.
Rejected recommendation to deploy newer 802.11ac routers for higher speed tiers to save costs.
Manipulated FCC results, temporarily give more ports to Cogent so as to improve their score.
League of Legends by Riot games requires low latency and packet loss, both were high (and higher compared to other NY ISPs) before Riot agreed to pay Spectrum.
Cherry picked other online content besides League to slow down more than others.

The Basic Problem

The Problem

Essentially, Spectrum was alleged to have used unethical and fraudulent ways to make profits. Now imagine that you just graduated from UB with a bachelor's degree in Computer Engineering/Computer Science and got hired by ForProfitOnly Internet provider. You're recruited into ForProfitOnly as a junior software engineer. It's your first day at work and your first assignment/task is to come up with routing algorithms to generate paths that will be used to route packets in ForProfitOnly's network topology. Since it's your first day at work, you're very eager to please your superiors by delivering as much revenue as possible to ForProfitOnly. Below is a detailed description of your task and the various problems that you need to solve.

Simplifications galore!

To make the problem more manageable, we have made many simplifying assumptions that at the same time hopefully capture the "essence" of the related fact in real-life. Wherever possible, we will provide more details that we are sweeping under the rug and if necessary provide a reference for further reading.

The Graph

You are given an undirected communication graph $G = (V,E)$ of the ForProfitOnly network, where a designated node $i \in V$ is the content provider (think of a service like Netflix). Every other node $u \in V$ is a router. $C$ is the set of clients and $C \subseteq V \setminus \{i\}$.

Clients vs. Routers

For this project, clients can still route packets but routers cannot be clients.

Every edge $e \in E$ has a delay $d_e$ associated with it, which is the amount of time it takes for a packet of data to traverse through an edge $e \in E$.

$d_e=1$ for all edges $e$

For all the problems, you can assume that for every $e \in E$, $d_e = 1$.

This is a simplification as in real life networks different edges can have different delays. We make this simplification to make the problems in this project easier.

Every client node in $C$ requests a packet of data from the content provider node $i \in V$. The packet addressed to a client $c \in C$ is denoted by $\text{pkt}_c$.

Packets are different

The packets $\text{pkt}_c$ for different clients $c$ are different. I.e. you cannot combine packets for different clients together.

One packet per client

We made the simplifying assumption that there is only one packet per client $c$. Unlike some of the other simplifications we make in this project, this is not such a big simplification.

For each of the problems 1-5 (see below), you will need to come up with an algorithm that outputs a path to route packets from the content provider node $i \in V$ to every client in $C$ with some given constraints.

Routing is centralized

In this project, there is a central algorithm that chooses an $i-c$ path for each client $c$. This is not how routing happens on the Internet. In particular, the TCP/IP protocol is a distributed protocol. However, distributed algorithms are out of the scope of this course.

Every problem will have an objective that you need to optimize.

Let $P$ be any path from the content provider node $i \in V$ to some client node $c \in C$. We define $d(P)$ (which we call path delay) to be the sum of the delay of all edges in path $P$. That is, $d(P) = \sum_{e \in P} d_e$. For every client $c\in C$, let $d(c)$ be the minimum of $d(P_c)$ among all $i-c$ paths $P_c$.

Let $P'_c$ be the actual $i-c$ path determined by your algorithm for client $c$. We use $D(P'_c)$ to denote the routing delay, which is the delay incurred by the routing algorithm (see below for more details on routing) when it routes all packes along $P'_c$ for all clients $c\in C$. Note that this is not necessarily the same as $d(P'_c)$.

Every node $u\in V$ has a bandwidth $b_u$, a bound on the number of packets it can send in each time step.

No bound on incoming traffic

Note that we are not putting any restriction on how many packets a router can receive in each time step. We make this simplification so that the problems are a bit simpler.

We will assume that the bandwidth of the ISP node is very large. That is, $b_i$ is a very large value

Walkthrough video

Here is a walkthrough video that summarizes the above material as well as gives a quick survey of the rest of the project (thanks to Snigdha Motadaka one of the Fall 21 TAs):

Routing of packets

Every client $c \in C$ has a priority, which is given by $\text{priority(c)}$.

Larger value is higher priority

$\text{priority(c)}$ is a positive integer and a larger value implies a higher priority.

By default, for all $c \in C$, $\text{priority(c)}$ = PRIORITY_DEFAULT = 0. You are not allowed to change/set the priority unless it is explicitly allowed in a problem.

The content provider node $i$ will send out a packet to all clients simultaneously. This packet will be routed through the path $P'_c$ for each client $c$ that your algorithm outputs.

All packets are sent out of $i$ at the same time

We make the simplifying assumption that packets $\text{pkt}_c$ for all clients $c$ are ready to be routed out of $i$ at the same time. This in real-life is not necessary since different clients might request their packets at different times. Again, this simplification makes the problems easier.

The routing will take place in time steps. That is, at every time step the packet will be transmitted to the next node in $P'_c$ until it reaches $c$. During the routing, if there is some router $u \in P'_c$ s.t. $u \neq c$ and $b_u$ is less than the number of packets that need to be transmitted a timestep, then $|b_u|$ number of packets belonging to clients of higher priority are transmitted in that timestep. Once the packet requested by client $c$ reaches it, $c$ will accept the packet.

Walkthrough video

Here is a walkthrough video that gives the algorithm idea of the routing algorithm (thanks to Aman Timalsina one of the Fall 21 TAs):

If you want to go into routing algorithm details, this is the walkthrough video for you (thanks to Aman Timalsina one of the Fall 21 TAs):

Algorithm Idea

The routing simulator will proceed iteratively, with each iteration mapping directly to a time ‘tick’. Inside each time tick, all the clients are processed and time is advanced only once this processing is finished.

The list of clients, initially maintained as an array (since linked list sorting is slow), will first be sorted by priority, which ensures only the highest priority packets get forwarded if there are bandwidth restrictions. The list is then converted to a Linked List so that as soon as a packet has reached, the client can be removed from the list.

The simulation iterates until all the packets have reached the end of their path. This condition is true when the list of clients is empty.

At each time tick, check if a packet has reached its destination. If it has, remove the client from the list of clients. The client’s delay is set to either the packet delay or infinity depending on whether the packet reached its intended client or not (respectively). Finally, skip to processing the next client.

If the packet is still in transit, its delay is incremented. It is then “forwarded” if the node it is currently at has enough bandwidth and after checking that the corresponding edge is valid. Forwarding comprises incrementing its location by 1 and decrementing the current node’s available bandwidth.

After each time tick, the bandwidth is reset to the router’s $b_u$ value for all routers that participated in the forwarding.

Once we are done processing the entire list, each client’s delay can be retrieved using the corresponding member variable.

Algorithm Details

Sort list_clients, key = client.priority and in descending order
Convert list_clients to a Linked List
active = set()
While list_clients is not empty:
- For client in list_clients:
  - current_node = node that the packet is currently at
  - If the client's packet has reached the end of it's path:
    - Remove client from list_clients
    - Client's delay is set to the packet delay if the current_node is the packet's intended client, otherwise it is set to ∞
    - Continue to next iteration
  - Increment packet delay
  - If current_node's bandwidth > 0:
    - If the current node and the next in the packet's path are not neighbors:
      - Remove client from list_clients
      - Client's delay = ∞
      - Continue to next iteration
    - Decrement current_node's bandwidth
    - Increment packet's current node to the next node in the packet's path
    - Add current_node to active
- For node in active:
  - Set node's bandwidth to node's original bandwidth
  - Clear all elements from active

Payments and Revenue

Every client $c \in C$ makes a payment $\text{pmt}_c$ to ForProfitOnly and also has a tolerance threshold $\alpha_c$, which represents $c$'s tolerance to slow internet. Please see Problem 1 for a detailed description.

Clients payments can vary

In this project we assume that the payment $\text{pmt}_c$ for different $c$ could be all different (unlike in real-life where typically there are "tiers" of payment).

Example 0

Let's look at a small example graph (please see the figure below) with $11$ nodes. Each node in this graph has a node id which is an integer. In this graph nodes $1,3,6,7,8$ are clients, node $0$ is the ISP node and the remaining nodes $2,4,5,9,10$ are routers. Also, every node's bandwidth is denoted as $b_{\text{<node id>}}$.

Let's say that the clients in this graph have the following payments: $\text{pmt}_1 = \$30, \text{pmt}_3 = \$40, \text{pmt}_6 = \$35, \text{pmt}_7 = \$40, \text{pmt}_8 = \$45$.

$d(c)$ in the above graph $G$

For the graph above, we have $d(1)=2, d(3)=2, d(6)=3, d(7)=4, d(8)=3$.

Below are five problems for you to solve. Problems 1-5 are cumulative. That is they build upon the previous problem and get progressively harder to solve.

The Problem

You just remembered what you learned in CSE 331 when trying to solve a problem: try to reduce it to a known problem that you've already seen. So this problem is a toy version of the actual problem and thus the constraints are not very harsh.

Now, each router "bandwidth" is set to infinity. In other words, routers can transmit as many packets concurrently as needed. All $\alpha_c$ is set to $1$, implying clients are not very tolerant of slow Internet. See the part on penalty for more details.

Input

You are given ForProfitOnly's communication graph $G = (V,E)$, the content provider node $i$, a set of clients $C\subseteq V \setminus \{i\}$, bandwidth size $b_u$ for every router $u$, and for all clients you are given their tolerance threshold, the payment they make, and their priorities (which are set to a default value). In summary, following is the input:

$G = (V, E)$
$i \in V$
$C$ s.t. $C \subseteq V \setminus \{i\}$
For all $u \in V \setminus \{i\}$, $b_u$ s.t. $b_u = \infty$
For all $c \in C$, $\alpha_c$ s.t. $\alpha_c = 1$
For all $c \in C$, $\text{priority(c)} =$ PRIORITY_DEFAULT

Penalty

The notion of penalty for this problem is the revenue loss that ForProfitOnly has to face. In this problem, it is possible to lose money only if some clients unsubscribe from ForProfitOnly due to its poor service (slow internet). A client $c \in C$ may unsubscribe from ForProfitOnly if $c$'s internet is slow enough to "beat" $c$'s tolerance threshold $\alpha_c$.

More precisely, let $P'_c$ be the $i-c$ path generated by your algorithm to route packets from $i$ to $c$. Then if $D(P'_c)$ exceeds $\alpha_c \cdot d(c)$, then $c$ unsubscribes from ForProfitOnly, and ForProfitOnly does not receive $c$'s payment $\text{pmt}_c$. This causes a drop in ForProfitOnly's revenue. Thus, the penalty that ForProfitOnly faces from client $c$ is either $\text{pmt}_c$ or nothing (which is 0). This calculation is done by the $pen_0$ function for each client $c \in C$. Below is a formal description of penalty function:

$pen_0(c, D(P'_c),\alpha_c, d(c),\text{pmt}_c)$ is the penalty function that accounts for the client/revenue loss that ForProfitOnly faces due to client $c \in C$. $pen_0$ has five inputs:
- client $c \in C$
- $D(P'_c)$ which is the total delay of $i-c$ path generated by your algorithm
- $\alpha_c$ which is the tolerance of client $c$
- $d(c)$ which is the minimum delay of any $i-c$ path
- $\text{pmt}_c$ for $c \in C$

If $D(P'_c) > \alpha_c \cdot d(c)$, then client $c$ unsubscribes from ForProfitOnly(and subscribes to some other ISP or say uses their cell phone as a way of connecting to the internet). So you lose their portion of the revenue. Otherwise, $pen_0(c,D(P'_c),\alpha_c,d(c),\text{pmt}_c)$ outputs $0$.

Thus, for this problem, $pen_0(c,D(P'_c),\alpha_c,d(c),\text{pmt}_c) = \begin{cases} \text{pmt}_c &\text{if} \quad D(P'_c) >\alpha_c \cdot d(c) \\ 0 &\text{ otherwise} \end{cases}$

Revenue

ForProfitOnly receives a payment $\text{pmt}_c$ from every client $c \in C$ unless $c$ has unsubscribed from ForProfitOnly's services. This means that ForProfitOnly receives nothing or a $0$ payment from any client $c$ who has unsubscribed from its services. Thus, we can define revenue from client $c$ as the payment received from $c$ minus the penalty faced due to $c$. This is calculation is done by the $rev$ function for each client $c \in C$. Below is a formal description of $rev$ function:

Let $rev(c, D(P'_c),\alpha_c,d(c),\text{pmt}_c)$ be the revenue received from client $c$. Here, $rev(c, D(P'_c),\alpha_c,d(c),\text{pmt}_c) = \text{pmt}_c - pen_0(c,D(P'_c),\alpha_c,d(c),\text{pmt}_c)$

Now that we defined revenue for each $c \in C$, we define total revenue to be the sum of the revenue received from each $c \in C$.

Thus, total revenue = $\sum_{c\in C} rev(c,D(P'_c),\alpha_c,d(c),\text{pmt}_c)$

Output

You need to come up with an algorithm that generates one $i-c$ path to route packets from $i$ to $c$, for each $c \in C$. You should output a list of $i-c$ paths for all $c \in C$. There can be multiple $i-c$ paths from $i$ to $c$, but your algorithm should generate an $i-c$ path that contributes towards satisfying the objective (see below) for this problem. To put it formally, you need to output:

$L_{P'}$ which is a list of $P'_c$ for all $c \in C$

Objective

Maximize total revenue (over all possible choices of $i-c$ paths for each $c\in C$).

Hint

The optimal solution for this problem is very closely related to a homework problem that y'all have already seen in this course.

Walkthrough video

Here is a walkthrough video that summarizes the above material and walks though some of the examples below (thanks to Aman Timalsina one of the Fall 21 TAs):

Example 1

A Solution

If the graph $G$ for this problem is our graph from Example 0, then here is a valid output (see the figure below):

That is, the output $L_{P'} = [P'_1,P'_3,P'_6,P'_7,P'_8]$. Where, $P'_1 = [0,10,1], P'_3 = [0,9,3], P'_6 = [0,9,3,6], P'_7 = [0,10,1,4,7], P'_8 = [0,9,3,8]$.

Since each $b_c = \infty$ ,for $c \in \{1,3,6,7,8\}$, the optimal routing protocol will incur a delay $d(c)$ for each $c$. This is because for each path P’_c, we will have $D(P'_c) = d(c)$ (see below for bit more details). Thus, for all $c \in C$, $pen_0(c) = 0$ because $D(P'_c) = d(c)$. So $rev(c) = \text{pmt}_c$, and thus total revenue would simply be the sum of payments from each client.

Justification for claim on revenue

Since all $b_c = \infty$, the routing protocol will incur a delay of $d(c)$. This is because for each path $P’_c$, we will have $D(P’_c)$ is the number of edges in $P'_c$ and further, for each $P’_c$ above, this is also $d(c)$. Thus, in this case we have $pen_0(c) = 0$. For example, we have $d(1)=2$, which is also the number of edges in $P'_2$: i.e. $D(P’_1) = 2$. Since $d(1)$ is the shortest possible delay we have found an optimal solution for path $P'_1$ and experience no penalty. A similar argument works for the rest of the clients.

Note that:

$D(P’_1) = 2 = d(1) $
$D(P’_3) = 2 = d(3) $
$D(P’_6) = 3 = d(6) $
$D(P’_7) = 4 = d(7) $
$D(P’_8) = 3 = d(8) $

So, total revenue $= \$30+ \$40 + \$35 + \$40 + \$45 = \$190$, which is the maximum possible revenue.

The Problem

Consider the allegation made by the NY AG against Spectrum on page 6 and point 4 from the AG's allegations

....Spectrum-TWC failed to deliver on this promise by leasing to a large number of its subscribers older-generation modems and wireless (or "WiFi") routers that it knew were incapable of achieving the promised Internet speeds. In addition, Spectrum-TWC failed to make adjustments to its network, such as reducing the size of service groups and increasing the number of channels for each service group, that would enable a subscriber to achieve the promised speeds. Not only did Spectrum-TWC fail to deliver the promised Internet speeds, it repeatedly assured subscribers that they could achieve the same results with wireless as with a wired connection, even when it knew that the wireless connection suffered from unavoidable, real-world limitations.

From the above allegation, Spectrum's routers seem to have had limited bandwidths that were incapable of providing the promised internet speeds to its customers.

In the previous toy problem, every router had an infinite bandwidth. This was a hypothetical assumption because there are some real-world limitations to the data transfer capacity (bandwidth). So for this problem, the bandwidth for each router will be limited.

Capturing bandwidth by a single number

As mentioned above there are many factors that determine the bandwidth for a client. In this project, we will capture this by a single number, i.e. the value $b_u$ for all $u\in V$.

Also, to be more realistic, the tolerance threshold for any client need not be 1, since different people have varying levels of patience.

Perfect knowledge of $\alpha_c$

In this project we will assume the prefect knowledge of $\alpha_c$ (as well as the related quantity $\beta_c$ that we will introduce in Problem 3), which is not possible in real life. We made this simplifying assumption to model the case that in real-life companies have data about their customers, which they can use to glean various information about them.

The allegation also says that Spectrum failed to make some necessary adjustments in its network that was necessary for it to deliver the promised internet speeds to its customers. Thus, the $i-c$ paths for all $c \in C$ that your algorithm generates could also determine how many of ForProfitOnly's clients are satisfied with its services.

Input

The input for the problem is the same as the previous one except for the bandwidth being limited and the tolerance threshold for every client being an arbitrary value greater than or equal to $1$. To put it formally, following is the input:

$G = (V, E)$
$i \in V$
$C$ s.t. $C \subseteq V \setminus \{i\}$
For all $u \in V \setminus \{i\}$, $b_u$ s.t. $b_u < \infty$
For all $c \in C$, $\alpha_c$ s.t. $\alpha_c \ge 1$
For all $c \in C$, $\text{pmt}_c$
For all $c \in C$, $\text{priority(c)} =$ PRIORITY_DEFAULT

Note

The highlighted input, is the part of the input that is different from the previous problem.

Penalty

Same as Problem 1

Revenue

Same as Problem 1

Output

Now given these real-world limitations, you should come up with an algorithm that generates $i-c$ paths for each client $c \in C$, in a way that contributes towards achieving the objective. Just like Problem 1, you should output a list of $i-c$ paths for all $c \in C$. That is, you need to output:

$L_{P'}$ which is a list of $P'_c$'s for all $c \in C$

Objective

Same as Problem 1.

Walkthrough video

Here is a walkthrough video that summarizes the above material and walks though some of the examples below (thanks to Alex Fernandez one of the Fall 21 TAs):

Example 2

A Solution

If the graph $G$ for this problem is our graph from Example 0, then here is a valid output:

Note

The $\alpha$ values given above will be used in the example graph for the remaining problems also (except for a small change to $\alpha_3$ in Problem 5).

That is, the output $L_{P'} = [P'_1,P'_3,P'_6,P'_7,P'_8]$. Where, $P'_1 = [0,10,1], P'_3 = [0,10,1,2,3], P'_6 = [0,10,1,5,6], P'_7 = [0,10,1,4,7], P'_8 = [0,9,3,8]$.

We will consider the paths given above to compute the penalties for each client. So for path $1$, $\alpha_1\cdot d(1)$ is $1 \cdot 2$, which is $2$. Next we compare that to our $D(P’_1)$, by finding the number of edges in each path and making sure that there is enough bandwidth to transfer packets each tick. If our $D(P’_c)$ is less than or equal to $\alpha_c\cdot d(c)$ value we receive no penalty. For notational convenience (in our worked out calculation below), if $D(P’_c) \leq \alpha_c \cdot d(c)$ we say “accept”, else “reject”.

Total Revenue

We claim that the revenue generated from the above solution is $\$155$ while the solution from Example 1 will generate a total revenue of $\$110$ for this input. Click the button below to see more details

See calculations for total revenue generated by above solution (as well as that for Example 1) for this problem

Determining $D(P')$ for every client

We claim that: $D(P’_1) = 2, D(P’_3) = 4, D(P’_6) = 4, D(P’_7) = 4, D(P’_8) = 3$. We verify this by tracing each time step in the routing simulation:

`At Time Tick $0$:`

Current: All packets at 0.

Passed on: All

`At Time Tick $1$:`

Current:

$\text{pkt}_1$ at node $10$
$\text{pkt}_3$ at node $10$
$\text{pkt}_6$ at node $10$
$\text{pkt}_7$ at node $10$
$\text{pkt}_8$ at node $9$

Passed on: All

`At Time Tick $2$:`

Current:

$\text{pkt}_1$ at node $1$
$\text{pkt}_3$ at node $1$
$\text{pkt}_6$ at node $1$
$\text{pkt}_7$ at node $1$
$\text{pkt}_8$ at node $3$

Reached: $\text{pkt}_1$

Passed on: $\text{pkt}_3, \text{pkt}_6, \text{pkt}_7,\text{pkt}_8$

`At Time Tick $3$:`

Current:

$\text{pkt}_3$ at node $2$
$\text{pkt}_6$ at node $5$
$\text{pkt}_7$ at node $4$
$\text{pkt}_8$ at node $8$

Reached: $\text{pkt}_8$

Passed on: $\text{pkt}_3, \text{pkt}_6, \text{pkt}_7$

`At Time Tick $4$:`

Current:

$\text{pkt}_3$ at node $3$
$\text{pkt}_6$ at node $6$
$\text{pkt}_7$ at node $7$

Reached: All packets have reached their destination so routing terminates.

Determining Penalty and Calculating total revenue

Now lets see what $pen_0$ function outputs for each client:

$pen_0(1) = 0$

$D(P’_1) = 2 , d(1) \cdot \alpha_1 = 2, 2 \leq 2$, so accept

$pen_0(3) = 0$

$D(P’_3) = 4 , d(3) \cdot \alpha_3 = 8, 4 \leq 8$, so accept

$pen_0(6) = 35$

$D(P’_6) = 4 , d(6) \cdot \alpha_6 = 3, 4 > 3$, so reject

$pen_0(7) = 0$

$D(P’_7) = 4 , d(7) \cdot \alpha_7 = 4, 4 \leq 4$, so accept

$pen_0(8) = 0$

$D(P’_8) = 3 , d(8) \cdot \alpha_8 = 3, 3 \leq 3$, so accept

Our total revenue is calculated by subtracting the summation of all penalties from our total possible revenue.

Total revenue $= 190 - 35 = 155$

Example 1 solution

The solution to Problem 1 is a worse solution for this problem. We will go through the calculations to see what total revenue generated by using Example 1's solution for this problem.

Solution to Example 1

In the above picture we use Example 1's solution to solve this problem. Now we will see, why this solution is worse for this problem.

Determining $D(P')$ for every client

We claim that: $D(P’_1) = 2, D(P’_3) = 2, D(P’_6) =4, D(P’_7) = 4, D(P’_8) = 5$. Let's now trace each time tick in the routing simulation:

`At Time Tick $0$:`

Current: All packets at 0.

Passed on: All

`At Time Tick $1$:`

Current:

$\text{pkt}_1$ at node $10$
$\text{pkt}_3$ at node $9$
$\text{pkt}_6$ at node $9$
$\text{pkt}_7$ at node $10$
$\text{pkt}_8$ at node $9$

Passed on: $\text{pkt}_1, \text{pkt}_3, \text{pkt}_7$

Delayed: $\text{pkt}_6, \text{pkt}_8$

`At Time Tick $2$:`

Current:

$\text{pkt}_1$ at node $1$
$\text{pkt}_3$ at node $3$
$\text{pkt}_6$ at node $9$
$\text{pkt}_7$ at node $1$
$\text{pkt}_8$ at node $9$

Reached: $\text{pkt}_1, \text{pkt}_3$

Passed on: $\text{pkt}_6, \text{pkt}_7$

Delayed: $\text{pkt}_8$

`At Time Tick $3$:`

Current:

$\text{pkt}_6$ at node $3$
$\text{pkt}_7$ at node $4$
$\text{pkt}_8$ at node $9$

Passed on: $\text{pkt}_6, \text{pkt}_7, \text{pkt}_8$

`At Time Tick $4$:`

Current:

$\text{pkt}_6$ at node $6$
$\text{pkt}_7$ at node $7$
$\text{pkt}_8$ at node $3$

Reached: $\text{pkt}_6, \text{pkt}_7$

Passed on: $\text{pkt}_8$

`At Time Tick $5$:`

Current:

$\text{pkt}_8$ at node $8$

Reached: $\text{pkt}_8$

NOTE: Some of the $D(P'_c)$ values have changed from the previous solution due to bandwidth restrictions.

Determining Penalty and Calculating total revenue

Now let us see what $pen_0$ function outputs for each client:

$pen_0(1) = 0$

$D(P’_1) = 2 , d(1) \cdot \alpha_1 = 2, 2 \leq 2$, so accept

$pen_0(3) = 0$

$D(P’_3) = 2 , d(3) \cdot \alpha_3 = 8, 2 \leq 8$, so accept

$pen_0(6) = 35$

$D(P’_6) = 4 , d(6) \cdot \alpha_6 = 3, 4 > 3$, so reject

$pen_0(7) = 0$

$D(P’_7) = 4 , d(7) \cdot \alpha_7 = 4, 4 \leq 4$, so accept

$pen_0(8) = 45$

$D(P’_8) = 5 , d(8) \cdot \alpha_8 = 3, 5 > 3$, so reject

So the total revenue $ = \$190 - (\$35 + \$45) = \$110$. Hence, this is definitely worse than the previous solution for this problem.

The Problem

Now consider this allegation made by the NY AG against Spectrum on page 9 and point 14 from the AG's allegations:

Spectrum-TWC fraudulently induced at least 640,000 subscribers in New York State to sign up for high-speed plans that it knew it could not provide. SpectrumTWC knowingly failed to allocate sufficient bandwidth to subscribers, which it could have done either by reducing the size of its service groups or adding more channels to each service group.

Thus for this problem, you are allowed to increase the bandwidth for every router, that is you can increase $b_u$ for all $u \in V \setminus \{i\}$ at a cost of $\$Z$ per increase in bandwidth.

Simplification/Motivation for $Z$

As alluded to above, increase the bandwidth for a node actually means changing the hardware and hence, this change has a real life cost. However, to simplify the problem we are assuming that there is a per-unit cost associated with increasing the bandwidths while in real life, these cost increases comes in quantums.

Let $X$ be the total increase of bandwidths over all routers. For any router $u \in V \setminus \{i\}$, let $b_u$ be its original bandwidth. And let $b'_u$ be the new increased bandwidth of $u$. If you chose not to increase the bandwidth of $u$, then $b_u = b'_u$. We define $X$ to be \[\sum_{u \in V \setminus \{i\}} \max(0,b'_u - b_u).\]

Why the $\max$ term?

The $\max$ term above seems un-necessary because one would expect $b'_u\ge b_u$. However, since your code will be outputting the $b'_u$ values, the $\max$ above makes it so that y'all have no incentive to make $b'_u<b_u$.

For this problem, we also introduce an additional parameter, $\beta_c$ which is the complaint threshold ($\beta_c \le \alpha_c$). A client $c$ may "complain" if $\beta_c \cdot d(c) < D(P'_c)$.

Can a client Complain and Unsubscribe at the same time?🤔

In a particular case where $D(P'_c) > \beta_c \cdot d(c)$ and $D(P'_c) > \alpha_c \cdot d(c)$, means that here the client $c$ both complains and unsubscribes from ForProfitOnly's services. In this case its a double whammy for ForProfitOnly.

Let $S$ be a subset of clients, and let $\rho_{\text{fcc}}$ and $\rho_{\text{lawsuit}}$ be a real numbers between $0$ and $1$. Let $Comp$ be a subset of clients in $S$ ($Comp \subseteq S$) that complain, that is for all $c \in Comp$, $D(P'_c) > \beta_c \cdot d(c)$ (and for $c\not\in Comp$, they do not satisfy this constraint).

If the size of $Comp$ is big enough, then it is safe to assume that the Office of the Attorney General will also have received a sizable number of complaints, prompting it to investigate potential wrongdoing and to consider filing a lawsuit to enforce laws that prohibit fraudulent or deceptive business practices and false advertising. In Spectrum's case, where since 2015 the OAG fielded over 2,800 reports from Spectrum's subscribers who complained about Spectrum's poor internet service.

A relevant allegation from the AG's summons and complaints that states this on page 12 and point 24:

Since 2015, the OAG has fielded over 2,800 reports from Spectrum-TWC subscribers who complained that they did not receive the Internet service promised to them in Spectrum-TWC advertisements.

And ultimately, a lawsuit was filed against Spectrum. In case you're curious about what the complaints from Spectrum's subscribers looked like, please see page 12 and point 25 of the AG's allegations . Now, this brings us to the first case of this problem.

Case 1 (Lawsuit): If $|Comp| \ge \lfloor \rho_{\text{lawsuit}} \cdot |C| \rfloor$, then a lawsuit will be filed against ForProfitOnly, and ForProfitOnly would end up paying an amount $\$A$ for settlement. (Also note that in this case we set $S=C$.)

When does OAG start an investigation?

The basic idea is that as the number of customer complaints increases, the likelihood of an enforcement action (lawsuit) by the Attorney General increases. This makes intuitive sense and seems to capture an important piece of how agencies decide whether to take action in the real world. That said, there are many other factors that influence a decision to bring a lawsuit – e.g. the possibility of deterrence by taking on a “high profile” target, the agency leadership’s idiosyncratic priorities, the political benefit to the agency, desire for good headlines, etc. So it can certainly happen that an enforcement action begins with only a few complaints—or even with none, if someone in the AG’s office chooses to undertake an investigation for some other reason. We stress that the above is a stylized model and that you shouldn’t assume that you can get away with breaking the law if you somehow manage to avoid complaints being filed.

Did you know? 🤔

In the real world, as per the way the deceptive-business-practice laws are structured, the court could impose non-monetary remedies (i.e. “injunctions”) for the victim (clients) if the company is found to have violated the law. That is the court could issue a court-order requiring the company to implement specific measures going forward in order to fix the deceptive/fraudulent practice. (E.g. ordering the company to swap out all D2 modems for D3 in Spectrum's case). These kinds of court-ordered changes will often be costly to implement, but the company must comply irrespective of how much it costs to do so. In the context of this problem, it is very likely (in the real world) for the court to order ForProfitOnly to increase the bandwidth of all routers if ForProfitOnly was found to have violated the law.

Did you know? 🤔

The court (in the real-world) may also impose a "flat rate" civil penalty of $\$5,000$ per violation of the the deceptive-business-practice laws. (Depending on what counts as a single "violation", this could theoretically end up being a huge number.)

Settlement

As noted above, the court has many options in how it could rule in a deceptive business practices case. In this project, we made the simplifying assumption that an out of court settlement would be reached. Indeed Spectrum ended up paying $\$174$ million on a lawsuit settlement .

We now move to the second case. In early 2013, the FCC administered internet speed tests and found that Spectrum did not deliver internet speeds that it promised. Here is the AG's allegation that states it (page 8 and point 10):

To conceal this failure, Spectrum-TWC assured the FCC in or about July 2013, that it would replace its older-generation modems for all of its subscribers, but in fact it did not. The FCC relied on that commitment to exclude the poor results of the speed tests on those modems in the FCC's subsequent public reports. Had these modems' results been included in the FCC's testing program, they would have revealed Spectrum-TWC's deceptive practices.

FCC's authority

We will assume that the FCC has separate legal authority to impose fines/penalties if it finds that an ISP is not delivering promised internet speeds, and further assume that the FCC is very strict about imposing such fines.

This brings us to case 2.

Case 2 (FCC testing): Now, the subset of clients $S$ is used by the FCC to test internet speeds. If $|Comp| \ge \lfloor \rho_{\text{fcc}} \cdot |S| \rfloor$, then the FCC would impose a legal fine amount $\$B$ that ForProfitOnly would have to pay.

Input

In addition to the input from the previous problem, you are given the subset $S$ of clients as an input, the complaint threshold $\beta_c$ for all $c \in C$, $\rho_{\text{lawsuit}}$ and $\rho_{\text{fcc}}$ corresponding to the two cases above, $\$A$ which is the lawsuit settlement amount, $\$B$ which is the FCC fine amount, and $\$Z$ as stated in the problem definition above. In summary, following is the input:

$G = (V, E)$
$i \in V$
$C$ s.t. $C \subseteq V \setminus \{i\}$
$S$ s.t. $S \subseteq C$
For all $u \in V \setminus \{i\}$, $b_u$ s.t. $b_u < \infty$
For all $c \in C$, $\alpha_c$ and $\beta_c$ s.t. $\alpha_c \geq \beta_c \geq 1$
For all $c \in C$, $\text{pmt}_c$
For all $c \in C$, $\text{priority(c)} =$ PRIORITY_DEFAULT
$\rho_{\text{lawsuit}}$, s.t. $0 \leq \rho_{\text{lawsuit}} \leq 1$
$\rho_{\text{fcc}}$, s.t. $0\leq \rho_{\text{fcc}}\leq 1$
$\$A$, which is the lawsuit amount.
$\$B$, which is the FCC fine amount
$\$Z$, which is the cost of unit increase in bandwidth

Note

The highlighted input is the part of the input that is different from the previous problem.

Penalty

The notion of penalties for this problem is two-fold. In addition to the loss of revenue if $D(P'_c)$ exceeds $\alpha_c \cdot d(c)$, if at least $\lfloor \rho \cdot |T| \rfloor$ number of clients in $T$ complain, then ForProfitOnly might have to pay a lawsuit settlement amount $\$A$ due to case 1 or a legal fine amount $\$B$ to the FCC due to case 2. The actual definition of $T$ will depend on which of the two cases is under consideration.

For $pen_0(c,D(P'_c),\alpha_c,d(c),\text{pmt}_c)$, please refer to Problem 1.

$pen_1(T,L_{P'},L_{\beta},L_{D},\rho, L)$ is the second penalty function that accounts for the additional penalty if the lawsuit is filed or FCC imposes a fine. $pen_1(T,L_{P'},L_{\beta},L_{D},\rho, L)$, has six input parameters:
- $T$ which is a subset of clients ($T \subseteq C$)
- $L_{P'}$ which is a list of $i-c$ paths for all $c \in T$
- $L_{\beta}$ which is a list of $\beta_c$ values for all $c \in T$
- $L_{D}$ which is a list of $d(c)$ values for all $c \in T$
- $\rho$ is a real number between $0$ and $1$.
- $L$ which is the legal penalty amount.
If at least $\lfloor \rho \cdot |T| \rfloor$ clients in $T$ complain (recall $c\in T$ complains if $D(P'_c) > \beta_c\cdot d(c)$), then $pen_1$ outputs $L$. Else $pen_1$ outputs $0$. We will use the same function $pen_1$ to model the penalties in both case 1 and case 2.

Revenue

The revenue obtained from each client is determined by the same rev function from Problem 1. Now, total revenue is defined separately for case 1 and case 2. For case 1, total revenue is defined as the sum of revenue obtained from each $c \in C$, minus the possible lawsuit settlement amount $\$A$ (here the set "$T$" needed in $pen_1$ is $C$) and $\$(X \cdot Z)$ which is the cost of increasing bandwidth (with $\rho=\rho_{\text{lawsuit}}$). For case 2, total revenue is defined as the sum of revenue obtained from each $c \in C$, minus the possible fine amount $\$B$ (here the set "$T$" is $S$ and $\rho=\rho_{\text{fcc}}$) imposed by the FCC and $\$(X \cdot Z)$ which is defined above. Below is a mathematical description of total revenue for both cases:

$rev(c,D(P'_c),\alpha_c,d(c),\text{pmt}_c)$ is the same as in Problem 1.

Total Revenue for case 1: $\left[ \sum_{c \in C} rev(c,D(P'_c),\alpha_c,d(c),\text{pmt}_c) \right] - \left[ pen_1(C,L_{P'},L_{\beta},L_{D},\rho_{\text{lawsuit}}, A) + (X \cdot Z) \right]$

Total Revenue for case 2: $\left[ \sum_{c \in C} rev(c,D(P'_c),\alpha_c,d(c),\text{pmt}_c) \right] - \left[ pen_1(S,L_{P'},L_{\beta},L_{D},\rho_{\text{fcc}}, B) + (X\cdot Z) \right]$
Total Revenue for both cases: For some inputs your code will have to handle both cases together, in which case the revenue will be $\left[ \sum_{c \in C} rev(c,D(P'_c),\alpha_c,d(c),\text{pmt}_c) \right] - \left[pen_1(C,L_{P'},L_{\beta},L_{D},\rho_{\text{lawsuit}}, A) + pen_1(S,L_{P'},L_{\beta},L_{D},\rho_{\text{fcc}}, B) + (X\cdot Z) \right]$

Note that we used the same $pen_1$ function (though with different parameters) to model the penalty due to lawsuit and FCC fines.

Output

As before you need to come up with an algorithm that generates $i-c$ paths for each $c \in C$, so you should output a list of $i-c$ paths for all $c \in C$. But for this problem you also need to output a list of bandwidth values for all routers (since you might have increased the bandwidth of some/all/no routers). To put it formally, you need to output:

$L_{P'}$ which is a list of $P'_c$'s for all $c \in C$

$L_{b'}$ which is a list of (updated) bandwidth $b'$ values for all $u \in V \setminus \{i\}$. Note that $X = \sum_u (b'_u-b_u)$.

What if $b'_u< b_u$ for some $u$?

The way $X$ is defined, if you make $b'_u<b_u$, then you will not "make" money by reducing the bandwidth. On the other hand, when computing the delays of your paths, the routing algorithm will use the smaller $b'_u$ value, which means your path might end up with a higher delay, which can only hurt you.

Objective

Same as Problem 1.

Walkthrough video

Here is a walkthrough video that summarizes the above material and walks though some of the examples below (thanks to Joseph Wu one of the Fall 21 TAs):

Example 3

Sample Input and Output

Now assume the input graph $G$ to be our example graph from Example $0$. Let's say that $\rho_{\text{fcc}} = 0.5, \rho_{\text{lawsuit}} = 0.4, B = \$70, A = \$100, Z = \$15, S = \{3,6\}$.

Then, here is a valid output for this problem with the given constraints:

That is, the output $L_{P'} = [P'_1,P'_3,P'_6,P'_7,P'_8]$. Where, $P'_1 = [0,10,1], P'_3 = [0,9,3], P'_6 = [0,9,3,6], P'_7 = [0,10,1,4,7], P'_8 = [0,9,3,8]$.

Updated Bandwidths: $(8,7,4,2,2,4,1,1,5,2,7)$. That is, the bandwidth of nodes $3$ and $9$ is increased by one unit.

Penalties and delays are calculated in the same way as before. In order to find our total we sum together all of the penalties received from each customer.

Total Revenue

The total revenue for the solution above is $\$160$ while the total revenue for the solutions from Examples 1 and 2 are -$\$60$ and $\$85$ respectively. Please click the button below for the details.

Click here to see the revenue generated by above solutions (as well as those from Example 1 and 2) for this problem

Determining $D(P')$ for every client

We claim that: $D(P’_1) = 2, D(P’_3) = 4, D(P’_6) =3, D(P’_7) = 4, D(P’_8) = 3$. Let's now trace each timestep in the routing of the packets.

`At Time Tick $0$:`

Current: All packets at 0.

Passed on: All

`At Time Tick $1$:`

Current:

$\text{pkt}_1$ at node $10$
$\text{pkt}_3$ at node $10$
$\text{pkt}_6$ at node $9$
$\text{pkt}_7$ at node $10$
$\text{pkt}_8$ at node $9$

Passed on: All

`At Time Tick $2$:`

Current:

$\text{pkt}_1$ at node $1$
$\text{pkt}_3$ at node $1$
$\text{pkt}_6$ at node $3$
$\text{pkt}_7$ at node $1$
$\text{pkt}_8$ at node $3$

Reached: $\text{pkt}_1$

Passed on: $\text{pkt}_3, \text{pkt}_6, \text{pkt}_7, \text{pkt}_8$

`At Time Tick $3$:`

Current:

$\text{pkt}_3$ at node $2$
$\text{pkt}_6$ at node $6$
$\text{pkt}_7$ at node $4$
$\text{pkt}_8$ at node $8$

Reached: $\text{pkt}_6, \text{pkt}_8$

Passed on: $\text{pkt}_3, \text{pkt}_7$

`At Time Tick $4$:`

Current:

$\text{pkt}_3$ at node $3$
$\text{pkt}_7$ at node $7$

Reached: All packets have reached their destination so routing terminates.

Determining Penalty

Now lets see what $pen_0$ function outputs for each client:

$pen_0(1) = 0$

$D(P’_1) = 2 , d(1) \cdot \alpha_1 = 2, 2 \leq 2$, so accept

$pen_0(3) = 0$

$D(P’_3) = 4 , d(3) \cdot \alpha_3 = 8, 4 \leq 8$, so accept

$pen_0(6) = 0$

$D(P’_6) = 3 , d(6) \cdot \alpha_6 = 3, 3 \leq 3$, so accept

$pen_0(7) = 0$

$D(P’_7) = 4 , d(7) \cdot \alpha_7 = 4, 4 \leq 4$, so accept

$pen_0(8) = 0$

$D(P’_8) = 3 , d(8) \cdot \alpha_8 = 3, 3 \leq 3$, so accept

Now let's see what the $pen_1$ function outputs. In order to discover whether or not a customer complains, we will first multiply $d(c)$ with the $\beta_c$ modifier. For path $d(1)$ that is $\beta_1 \cdot d(1) = 1 \cdot 2$, which is $2$. Next we compare that to our $D(P’_1)$ which is $2$. Since our $D(P’_1)$ is not less than our $\beta_1 \cdot D(1)$, the customer does not complain. In the same way, we can check this for all other clients:

Client Node 1	$D(P'_1)=2, \beta_1 \cdot d(1)=2$	does not complain
Client Node 3	$D(P'_3)=4, \beta_3 \cdot d(3)=4$	does not complain
Client Node 6	$D(P'_6)=3, \beta_6 \cdot d(6)=3$	does not complain
Client Node 7	$D(P'_7)=4, \beta_7 \cdot d(7)=4$	does not complain
Client Node 8	$D(P'_8)=3, \beta_8 \cdot d(8)=3$	does not complain

Calculating total revenue

Total Complains:

FCC: 0

Lawsuit:0

Now that we have our total of complaining customers we find the fraction of the group they represent and compare it to our $\rho$ values (i.e. $\rho_{\text{lawsuit}}$ and $\rho_{\text{fcc}}$ for the two cases). If the fraction of complaining clients $> \rho$, then no fine is awarded.

FCC: $\frac{0}{5} < 0.5$, i.e., NO fine

Lawsuit: $\frac{0}{5} < 0.4$, i.e., NO lawsuit

Thus, $pen_1 = 0$ (for both cases).

Now, in order to calculate the revenue we subtract $pen_0$ and $pen_1$, and our bandwidth changes from our total possible revenue.

So, total revenue $= \$190 - \$0 - \$0 - (2 \cdot \$15) = \$160 $

Example 1 solution

Both Example 1 and Example 2 solutions will be a worse solutions for this problem.

The figure below shows Example 1's solution being used to solve this problem.

NOTE: In problem 1 there was no increase of bandwidth for any router.

Now here is a quick reference to Example 1's solution: $P'_1 = [0, 10, 1], P'_3 = [0, 9, 3], P'_6 = [0, 9, 3, 6], P'_7 = [0, 10, 1, 4, 7], P'_8 = [0, 9, 3, 8]$ and $D(P’_1) = 2, D(P’_3) = 2, D(P’_6) =4, D(P’_7) = 4, D(P’_8) = 4$

The total $pen_0$ across all clients remains the same as Problem 2: $\$80$ ($pen_0(1)=0,pen_0(3)=0,pen_0(6)=35,pen_0(7)=0,pen_0(8)=45$). Now, $pen_1$ outputs the following:

Client Node 1	$D(P'_1)=2, \beta_1 \cdot d(1)=2$	does not complain
Client Node 3	$D(P'_3)=2, \beta_3 \cdot d(3)=4$	does not complain
Client Node 6	$D(P'_6)=4, \beta_6 \cdot d(6)=3$	Complains!
Client Node 7	$D(P'_7)=4, \beta_7 \cdot d(7)=4$	does not complain
Client Node 8	$D(P'_8)=4, \beta_8 \cdot d(8)=3$	Complains!

Calculating Revenue

Now let's compare our results with the corresponding $\rho$ values and see if fines occur:

FCC: $\frac{1}{2} \ge 0.5$

Lawsuit: $\frac{2}{5} \ge 0.4$

Thus, both the settlement amount and FCC fine have to be paid and this, $pen_1 = \$170$, so total revenue $= \$190 - \$170 - \$80 -\$0= -\$60$.

Example 2 solution

The figure below shows Problem 2's example solution being used to solve this problem.

NOTE: In problem 2 there was no increase of bandwidth for any router.

For a quick reference, these were the delay's produced by our solution algorithm for Problem 2's example: $D(P’_1) = 2, D(P’_3) = 4, D(P’_6) = 4, D(P’_7) = 4, D(P’_8) = 3$. And the output of the $pen_0$ function for clients in Problem 2 was: $pen_0(1) = 0, pen_0(3) = 0, pen_0(6) =35, pen_0(8) = 0$.

Problem 2 did not have the $pen_1$ function unlike this problem. So let's see what $pen_1$ outputs with our solutions for Problem 2.

Client Node 1	$D(P'_1)=2, \beta_1 \cdot d(1)=2$	does not complain
Client Node 3	$D(P'_3)=4, \beta_3 \cdot d(3)=4$	does not complain
Client Node 6	$D(P'_6)=4, \beta_6 \cdot d(6)=3$	Complains!
Client Node 7	$D(P'_7)=4, \beta_7 \cdot d(7)=4$	does not complain
Client Node 8	$D(P'_8)=3, \beta_8 \cdot d(8)=3$	does not complain

Calculating total revenue

Total Complains

Lawsuit: 1 and FCC = 1. Now, by comparing the corresponding $\rho$ values we get:

FCC: $\frac{1}{2} \ge 0.5$, i.e., there is a fine.

Lawsuit: $\frac{1}{5} < 0.4$, i.e., there is no lawsuit. Thus, $pen_1$ outputs $\$70$. So the total revenue $ = \$190 - \$70 - \$35 - \$0 = \$85$.

Another Input

Currently, we are able to avoid both the FCC fine and the lawsuit fines. This will not always be the case, consider if $Z = \$45$ and $B = \$40$. In this case the total revenue for the Example 3 solution becomes $=\$190-2\cdot\$45=\$100$. By contrast Example 2 solution becomes the better solution.

Click here to see how Example 2 solution will be a better solution for this problem with the $Z$ and $B$ values given above

Below is a picture showing Example 2 solution being used to solve the above updated problem:

Problem 2 did not have the $pen_1$ function unlike this problem. So let's see what $pen_1$ outputs with our solutions for Problem 2. (This is the same calculation that we did above for the earlier input-- nothing changes.)

Client Node 1	$D(P'_1)=2, \beta_1 \cdot d(1)=2$	does not complain
Client Node 3	$D(P'_3)=4, \beta_3 \cdot d(3)=4$	does not complain
Client Node 6	$D(P'_6)=4, \beta_6 \cdot d(6)=3$	Complains!
Client Node 7	$D(P'_7)=4, \beta_7 \cdot d(7)=4$	does not complain
Client Node 8	$D(P'_8)=3, \beta_8 \cdot d(8)=3$	does not complain

Calculating total revenue

Lawsuit: 1 and FCC = 1. Now, by comparing the corresponding $\rho$ values we get:

FCC: $\frac{1}{2} \ge 0.5$, i.e., there is a fine.

Lawsuit: $\frac{1}{5} < 0.4$, i.e. there is no lawsuit. Thus, $pen_1$ outputs $\$40$. So the total revenue $ = \$190 - \$40 - \$35 - \$0 = \$115$, which is better than the revenue of $\$100$ from the Example 3 solution.

The Problem

For this problem, you are allowed to set/change $\text{priority(c)}$ for all $c \in C$.

Coming back to the story of Spectrum, NY AG alleged Spectrum knowingly took full advantage of the fact that its subscribers had very few choices for some other ISP. Thus, this essentially forced many of Spectrum's subscribers to stick with Spectrum. But nevertheless, Spectrum continued to deceive its subscribers. Here is the relevant allegation against Spectrum by the AG that states it (page 12 and point 23):

Throughout the Relevant Period, Spectrum-TWC consistently failed to make the investments necessary to provide its subscribers with the Internet speeds and reliable online content that it had promised. Capitalizing on the fact that its subscribers had few, if any, other choices for an ISP, Spectrum-TWC placed profits ahead of the interests of its subscribers, and collected billions of dollars in fees from New York subscribers for providing Internet service.

Now, for this problem, you are given a subset $R$ of clients that live in rural areas where ForProfitOnly is a monopoly. Thus, every rural client has an infinite tolerance threshold, because rural clients will never unsubscribe from ForProfitOnly's services even if they are unhappy with the service because they simply do not have any other choice. However, rural clients can still complain. As per the above AG's allegation, Spectrum took advantage of the fact that it was a monopoly in the region.

Did you know? 🤔

The court may also order for the disgorgement of revenues that resulted from fraudulent and illegal practices (i.e. company has to turn over illegally gotten gains). In our problem, although the rural clients cannot unsubscribe (but of course they can complain) from ForProfitOnly's services, in the real-world if these complains are forwarded to the Office of the Attorney General (OAG), then it is very much likely that ForProfitOnly would have to turn over illegally gotten gains with interest to those affected by the action.

Input

In addition to the input from the previous problem, you are given the subset $R$ of rural clients such that, for each client $c \in R$, $\alpha_c$ is set to $\infty$. In summary, following is the input for this problem:

Graph $G = (V, E)$
$i \in V$
For all $u \in V \setminus \{i\}$, $b_u$ s.t. $b_u < \infty$
For all $c \in C$, $\alpha_c$ and $\beta_c$ s.t. $\alpha_c \geq \beta_c \geq 1$
For all $c \in C$, $\text{pmt}_c$
$S$ s.t. $S \subseteq C$
$\rho_{\text{lawsuit}}$ s.t. $0 \leq \rho_{\text{lawsuit}} \leq 1$
$\rho_{\text{fcc}}$ s.t. $0 \leq \rho_{\text{fcc}} \leq 1$
$\$A$, which is the lawsuit settlement amount
$\$B$, which is the FCC fine amount
$R$, the set of rural clients s.t. $R \subseteq C$
For all $c \in R$, $\alpha_c = \infty$.
For all $c \in C$, $\text{priority(c)} =$ PRIORITY_DEFAULT
$\$Z$, which is the cost of unit increase in bandwidth

Note

The highlighted input is the part of the input that is different from the previous problem.

Penalty

Same as Problem 3.

Revenue

Same as Problem 3.

Output

Again, for this problem you should output a list of $i-c$ paths for all $c \in C$ generated by your algorithm, a list of $\text{priority(c)}$ for all $c \in C$ (since you might have changed the priority of some/all/no clients in $C$), and like the previous problem a list of bandwidth values for all routers. To put it formally, you should output:

$L_{P'}$, which is a list of $P'_c$'s for all $c \in C$
$L_{priority}$, which is a list of $\text{priority(c)}$ values for all $c \in C$
$L_{b'}$, which is a list of new bandwidth values $b'_u$ values for all $u \in V \setminus \{i\}$. As in Problem 3, $X = \sum_u (b'_u-b_u)$

Objective

Same as Problem 1.

Did you know? 🤔

All the possible monetary and non-monetary remedies (that can possibly be imposed by the court for a violation of the deceptive-business-practice laws ) described in all the Did you know's can also be imposed cumulatively by the court!

Walkthrough video

Here is a walkthrough video that summarizes the above material and walks though some of the examples below (thanks to Aman Timalsina one of the Fall 21 TAs):

Example 4

Sample Input and Output

Now assume the input graph $G$ to be our example graph. Let's say that $\rho_{\text{fcc}} = 0.5, \rho_{\text{lawsuit}} = 0.4, B = \$70, A = \$100, Z = \$15, S = \{3,6\}$ same as our example for Problem 3. And now, let's say that $R = \{8\}$.

Then, here is a valid output for this problem with the given constraints (no bandwidth values are changed and neither are the packets' priorties):

That is, the output $L_{P'} = [P'_1,P'_3,P'_6,P'_7,P'_8]$. Where, $P'_1 = [0,10,1], P'_3 = [0,10,1,2,3], P'_6 = [0,9,3,6], P'_7 = [0,10,1,4,7], P'_8 = [0,10,1,5,8]$.

Delays and penalties are calculated almost the same as before, with one caveat, if a rural client complains they do not drop service and thus, no penalty is felt for $pen_0$.

Total Revenue

The total revenue generated from the above solution is $\$190$ while the solutions from Examples 1, 2 and 3 generate total revenues of $-\$15$, $\$95$ and $\$160$ respectively. Please click the button below for the detailed calculations.

Click here to see the revenue calculation for the above solution as well as those from Examples 1, 2 and 3

Determining $D(P')$ values

We claim that: $D(P’_1) = 2, D(P’_3) = 4, D(P’_6) =3, D(P’_7) = 4, D(P’_8) = 4$. Let's now trace each timestep in the routing of the packets.

`At Time Tick $0$:`

Current: All packets at 0.

Passed on: All

`At Time Tick $1$:`

Current:

$\text{pkt}_1$ at node $10$
$\text{pkt}_3$ at node $10$
$\text{pkt}_6$ at node $9$
$\text{pkt}_7$ at node $10$
$\text{pkt}_8$ at node $10$

Passed on: All

`At Time Tick $2$:`

Current:

$\text{pkt}_1$ at node $1$
$\text{pkt}_3$ at node $1$
$\text{pkt}_6$ at node $3$
$\text{pkt}_7$ at node $1$
$\text{pkt}_8$ at node $1$

Reached: $\text{pkt}_1$

Passed on: $\text{pkt}_3, \text{pkt}_6, \text{pkt}_7, \text{pkt}_8$

`At Time Tick $3$:`

Current:

$\text{pkt}_3$ at node $2$
$\text{pkt}_6$ at node $6$
$\text{pkt}_7$ at node $4$
$\text{pkt}_8$ at node $5$

Reached: $\text{pkt}_6$

Passed on: $\text{pkt}_3, \text{pkt}_7, \text{pkt}_8$

`At Time Tick $4$:`

Current:

$\text{pkt}_3$ at node $3$
$\text{pkt}_7$ at node $7$
$\text{pkt}_8$ at node $8$

Reached: All packets have reached their destination so routing terminates.

Determining Penalty

Now lets see what $pen_0$ function outputs for each client:

NOTE: For any client $c$, if $c \in R$, then $pen_0(c) = 0$ since we have $\alpha_c=\infty$

$pen_0(1) = 0$

$D(P’_1) = 2 , d(1) \cdot \alpha_1 = 2, 2 \leq 2$, so accept

$pen_0(3) = 0$

$D(P’_3) = 4 , d(3) \cdot \alpha_3 = 8, 4 \leq 8$, so accept

$pen_0(6) = 0$

$D(P’_6) = 3 , d(6) \cdot \alpha_6 = 3, 3 \leq 3$, so accept

$pen_0(7) = 0$

$D(P’_7) = 4 , d(7) \cdot \alpha_7 = 4, 4 \leq 4$, so accept

$pen_0(8) = 0$

$D(P’_8) = 4 , d(8) \cdot \alpha_8 = \infty, 4 \le \infty$. So accept.

Now let's see what the $pen_1$ function outputs. The $pen_1$ function works in the same way as Problem 3

Client Node 1	$D(P'_1)=2, \beta_1 \cdot d(1)=2$	does not complain
Client Node 3	$D(P'_3)=4, \beta_3 \cdot d(3)=4$	does not complain
Client Node 6	$D(P'_6)=3, \beta_6 \cdot d(6)=3$	does not complain
Client Node 7	$D(P'_7)=4, \beta_7 \cdot d(7)=4$	does not complain
Client Node 8	$D(P'_8)=4, \beta_8 \cdot d(8)=3$	complains

Calculating total revenue

Below are the total number of complaints for the two cases:

FCC: $0$

Lawsuit: $1$

Now that we have our total of complaining customers we find the fraction of the group they represent and compare it to our $\rho$ values. If the fraction of complaining clients < $\rho$ , then no fine is awarded.

FCC: $\frac{0}{5} < 0.5$, i.e., NO fine

Lawsuit: $\frac{1}{5} < 0.4$, i.e., NO lawsuit

Thus, $pen_1 = 0$ (for both cases).

Now, in order to calculate the revenue we subtract $pen_0$ and $pen_1$, and our bandwidth changes from our total possible revenue.

So, total revenue $= \$190 - \$0 - \$0 = \$190 $

Note

If we change $\rho_{\text{lawsuit}}$ to be $0.2$ (the remaining input is unchanged). Then $pen_1$ would result in the following:

FCC: $\frac{0}{2} > 0.5$, i.e., no fine is levied.

Lawsuit: $\frac{1}{5} \ge 0.2$, i.e., a lawsuit occurs.

So total revenue $ = \$190 - \$0 - \$100 = \$90 $

Example 1 solution

Now let's see how our results from previous examples compare on the same input as above. For examples 1 and 2 we will use just the paths and there will be no bandwidth changes or priorities taken into account since this was not defined in their example. Example 3 will have bandwidths increases but no priorities are changed.

To start with, let's use Example 1's solution for this problem (see figure below):

$pen_0$ will be calculated exactly the same way as we computed it for Example 1's solution for problem in Example 2 except as $8$ is a rural client, the penalty is only $\$35$. And for $pen_1$:

Client Node 1	$D(P'_1)=2, \beta_1 \cdot d(1)=2$	does not complain
Client Node 3	$D(P'_3)=2, \beta_3 \cdot d(3)=4$	does not complain
Client Node 6	$D(P'_6)=4, \beta_6 \cdot d(6)=3$	complains
Client Node 7	$D(P'_7)=4, \beta_7 \cdot d(7)=4$	does not complain
Client Node 8	$D(P'_8)=5, \beta_8 \cdot d(8)=3$	complains

Now, lets compare the results with the corresponding $\rho$ values to see if a fine occurs:

FCC: $\frac{1}{2} \ge 0.5$, i.e., there is a fine.

Lawsuit: $\frac{2}{5} \ge 0.4$, i.e., a lawsuit occurs.

So, $pen_1 = \$100 + \$70 = \$170$. And thus the total revenue $= \$190 - \$170 - \$35 = -\$15$. This is clearly a worse solution for this problem.

Example 2 solution

The picture below shows Example 2's solution being used to solve this problem:

Like Example 2 only $pen_0(6)=\$35$, and $pen_0$ for all other clients outputs $0$. Let's now see what $pen_1$ outputs:

Client Node 1	$D(P'_1)=2, \beta_1 \cdot d(1)=2$	does not complain
Client Node 3	$D(P'_3)=4, \beta_3 \cdot d(3)=4$	does not complain
Client Node 6	$D(P'_6)=4, \beta_6 \cdot d(6)=3$	complains
Client Node 7	$D(P'_7)=4, \beta_7 \cdot d(7)=4$	does not complain
Client Node 8	$D(P'_8)=3, \beta_8 \cdot d(8)=3$	does not complain

Now, lets compare the results with the corresponding $\rho$ values to see if a fine occurs:

FCC: $\frac{1}{2} \ge 0.5$, i.e., a fine is levied.

Lawsuit: $\frac{1}{5} < 0.4$, i.e., no lawsuit happens.

So, $pen_1 = \$70$. And thus the total revenue $= \$190 - \$70 - \$35 = \$95$. This is clearly a worse solution for this problem.

Example 3 solution

The picture below shows Example 3's solution being used to solve this problem:

$pen_0$ and $pen_1$ both turn out to be $\$0$ as in Example 3 so total revenue $ = \$190 - \$0 -\$0 - (2 \cdot \$15) = \$160$. Again this is worse than our solution for Example 4.

The Problem

Like Spectrum, ForProfitOnly gets hit with multiple lawsuits and you decide it is a good time to work for another company where profit is not the only motive. Luckily for you, a new startup EthicalInternet promises to keep customers first and then worry about profit. More precisely, EthicalInternet will guarantee that no customer would complain/drop-out. You apply for a position at EthicalInternet and you get the job: congratulations! You have a similar problem to solve as you did when you were at ForProfitOnly but now your objectives are different.

For this problem, there is no notion of a complaining client (but see the definition of penalty for how we will ensure that no customer would dropout). You are still allowed to set/change the priority for every client, and increase the bandwidth for any router at a cost of $\$Z$ per increase in bandwidth like before.

Input

$G = (V, E)$
$i \in V$
$C$ s.t. $C \subseteq V \setminus \{i\}$
For all $u \in V \setminus \{i\}$, $b_u$ s.t. $b_u < \infty$
For all $c \in C$, $\alpha_c$ s.t. $\alpha_c \ge 1$
For all $c \in C$, $\text{pmt}_c$
For all $c \in C$, $\text{priority(c)} =$ PRIORITY_DEFAULT
$\$Z$, which is the cost of unit increase in bandwidth

Penalty

The notion of penalty for this problem is different from all the previous problems. If there exists even one client $c \in C$ s.t. $D(P'_c) > \alpha_c \cdot d(c)$, then EthicalInternet will not charge any of its clients -- i.e. its revenue would be $0$.

Keeping customers first

The condition of making sure for every $c$ we have $D(P'_c)\le \alpha_c\cdot d(c)$ is probably a strong guarantee-- we picked it because of its simplicity. One could envision another version of this problem, where one could charge customers proportional to $\frac{d(c)}{D(P'_c)}$. This way you do get some revenue if some customer gets a slow service but in that case customers with slower speeds would pay less compared with those who get faster speeds. However, in the latter case there might still be an incentive to say give no service to some clients at all, if it sped up other customer's service.

Here is a questions for y'all to ponder on: if you owned EthicalInternet, what metric would you use to ensure a "minimum happiness" for your customers?

Unlike the previous problem, we will directly define the revenue without explicitly defining a penalty function since it makes the description much simpler.

Revenue

Total revenue is defined as the sum of payments received from each client $c \in C$ (minus $X\cdot Z$, where $X$ is as defined in Problem 3) if there is no client $c \in C$ such that $D(P'_c)> \alpha\cdot d(c)$. But if there is a client $c \in C$ with this property, then the total revenue would be $-X\cdot Z$. To put it mathematically:

Total Revenue $= \begin{cases} \sum_{c \in C} \text{pmt}_c -X\cdot Z &\text{if there is no} \quad c \in C \quad \text{s.t.} \quad D(P'_c) > \alpha_c \cdot d(c) \\ -X\cdot Z &\text{ otherwise} \end{cases}$

Output

Same as Problem 4.

Objective

Same as Problem 1.

Walkthrough video

Here is a walkthrough video that summarizes the above material and walks though some of the examples below (thanks to Aman Timalsina one of the Fall 21 TAs):

Example 5

Note

We use the same graph as the previous examples, though we no longer care about $\beta$ values or if a client is rural or not. Please also note that $\alpha_3$ has been reduced from $4$ to $1.75$. We realize this is not an integer (as the $\alpha$ values are supposed to be but we make this change for illustration purposes only-- as otherwise we'll need to change more things. In your submission can and should assume that all $\alpha_c$ values are positive integers.

Now assume the input graph $G$ to be our example graph. Then here (see figure below) is a valid output for this problem with the given constraints:

NOTE:We use the same $Z=\$15$ value as stated in the example solution for Problem 3.

That is, the output $L_{P'} = [P'_1,P'_3,P'_6,P'_7,P'_8]$. Where, $P'_1 = [0,10,1], P'_3 = [0,9,3], P'_6 = [0,9,3,6], P'_7 = [0,10,1,4,7], P'_8 = [0,9,3,8]$.

Updated Bandwidths: $(8,7,4,2,2,4,1,1,5,2,7)$. That is, the bandwidth of nodes $3$ and $9$ is increased by one unit.

Priorities: $\text{priority(1)} = 1, \text{priority(3)} = 0, \text{priority(6)} = 2, \text{priority(7)} = 3, \text{priority(8)} = 4 $. (Recall that larger values implies higher priority.)

Total Revenue

For the solution above, we get a total revenue of $\$160$ while the solutions from Examples 1, 2, 3 and 4 get revenues of $\$0$, $\$0$, $-\$30$ and $\$0$ respectively. Please click on the button below to see details of the calculations.

Click here to see the revenue calculation for the above solution (as well as those of Example 1, 2, 3 and 4 solutions)

Determining $D(P')$ for every client

Since we now take into account priority, $D(P’_c)$ will be calculated a little differently. At every tick of the simulator we will attempt to pass on as many packets as possible starting with those of highest priority and moving to those with lowest priority. If we don’t have enough bandwidth, the lower priority packet is delayed another tick adding one to its total delay. Now, let's track each time tick of the routing of the packets:

`At Time Tick $0$:`

Current: All packets at 0.

Passed on: All

`At Time Tick $1$:`

Current:

$\text{pkt}_1$ at node $10$
$\text{pkt}_3$ at node $9$
$\text{pkt}_6$ at node $9$
$\text{pkt}_7$ at node $10$
$\text{pkt}_8$ at node $9$

Passed on: $\text{pkt}_1, \text{pkt}_6, \text{pkt}_7, \text{pkt}_8$

Delayed: $\text{pkt}_3$ (as $3$ has lower priority than $6$ and $8$)

`At Time Tick $2$:`

Current:

$\text{pkt}_1$ at node $1$
$\text{pkt}_3$ at node $9$
$\text{pkt}_6$ at node $3$
$\text{pkt}_7$ at node $1$
$\text{pkt}_8$ at node $3$

Reached: $\text{pkt}_1$

Passed on: $\text{pkt}_3, \text{pkt}_6, \text{pkt}_7, \text{pkt}_8$

`At Time Tick $3$:`

Current:

$\text{pkt}_3$ at node $3$
$\text{pkt}_6$ at node $6$
$\text{pkt}_7$ at node $4$
$\text{pkt}_8$ at node $8$

Reached: $\text{pkt}_3, \text{pkt}_6, \text{pkt}_8$

Passed on: $\text{pkt}_7$

`At Time Tick $4$:`

Current:

$\text{pkt}_7$ at node $7$

Reached: All packets reached.

The delay of the path is now equivalent to the tick that it reached its destination, i.e. $D(P'_1)=2, D(P'_3)=3, D(P'_6)=3, D(P'_7)=4, D(P'_8)=3$.

Revenue Calculation

If $D(P’_c) \leq \alpha_c \cdot d(c)$ then accept, else reject. Reject means the customer complains, so if we experience any rejections we earn no revenue from clients. Now let us see if there is an client $c \in \{1,3,6,7,8\}$ such that $c$ would be rejected:

$D(P’_1) = 2$

$d(1) \cdot \alpha_1 = 2 \cdot 1$
$2 \leq 2$, accept

$D(P’_3) = 3$

$d(3) \cdot \alpha_3 = 2 \cdot 1.75$
$3 \lt 3.5$, accept

$D(P’_6) = 3$

$d(6) \cdot \alpha_6 = 3 \cdot 1$
$3 \leq 3$, accept

$D(P’_7) = 4$

$d(7) \cdot \alpha_7 = 4 \cdot 1$
$4 \leq 4$, accept

$D(P’_8) = 3$

$d(8) \cdot \alpha_8 = 3 \cdot 1$
$3 \leq 3$, accept

Thus, total revenue $ = \left[ \sum_{c \in \{1,3,6,7,8\}} \text{pmt}_c \right] - \text{bandwidth increase} = \$190 - (2 \cdot \$15) = \$160$

Alternate Solution with different priorities

Now, let’s say we shift the priorities such that (among others) client $3$ now has the highest priority:

Changed Priorities: $\text{priority(1)} = 0, \text{priority(3)} = 4, \text{priority(6)} = 2, \text{priority(7)} = 1, \text{priority(8)} = 3 $.

Redetermining $D(P')$ for every client after changing priorities

Let us re-run the routing of the packets with the new priorities to compute the new delays:

`At Time Tick $0$:`

Current: All packets at 0.

Passed on: All

`At Time Tick $1$:`

Current:

$\text{pkt}_1$ at node $10$
$\text{pkt}_3$ at node $9$
$\text{pkt}_6$ at node $9$
$\text{pkt}_7$ at node $10$
$\text{pkt}_8$ at node $9$

Passed on: $\text{pkt}_1, \text{pkt}_3, \text{pkt}_7, \text{pkt}_8$

Delayed: $\text{pkt}_6$ since now $6$ has lower priority than $3$ and $8$

`At Time Tick $2$:`

Current:

$\text{pkt}_1$ at node $1$
$\text{pkt}_3$ at node $3$
$\text{pkt}_6$ at node $9$
$\text{pkt}_7$ at node $1$
$\text{pkt}_8$ at node $3$

Reached: $\text{pkt}_1, \text{pkt}_3$

Passed on: $\text{pkt}_6, \text{pkt}_7, \text{pkt}_8$

`At Time Tick $3$:`

Current:

$\text{pkt}_6$ at node $3$
$\text{pkt}_7$ at node $4$
$\text{pkt}_8$ at node $8$

Reached: $\text{pkt}_8$

Passed on: $\text{pkt}_6, \text{pkt}_7$

`At Time Tick $4$:`

Current:

$\text{pkt}_6$ at node $6$
$\text{pkt}_7$ at node $7$

Reached: $\text{pkt}_6, \text{pkt}_7$

Thus, the delays for the chosen paths are $D(P'_1)=2, D(P'_3)=2, D(P'_6)=4, D(P'_7)=4, D(P'_8)=3$.

Recalculating total revenue

Now, again let's check if there is a client $c \in \{1,3,6,7,8\}$ such that $D(P'_c) \gt \alpha_c \cdot d(c)$:

$D(P’_1) = 2$

$d(1) \cdot \alpha_1 = 2 \cdot 1$
$2 \leq 2$, accept

$D(P’_3) = 2$

$d(3) \cdot \alpha_3 = 2 \cdot 1.75$
$2 \leq 3.5$, accept

$D(P’_6) = 4$

$d(6) \cdot \alpha_6 = 3 \cdot 1$
$4 > 3$, reject

$D(P’_7) = 4$

$d(7) \cdot \alpha_7 = 4 \cdot 1$
$4 \leq 4$, accept

$D(P’_8) = 3$

$d(8) \cdot \alpha_8 = 3 \cdot 1$
$3 \leq 3$, accept

Since at least one customer complained we make no money, and on top of that we end up losing money since we must still pay for the bandwidth increase.

So, total revenue$= \$0 - (2 \cdot \$15) = -\$30$.

Comparing with previous solutions

Now we will compare our current solution, to those for previous examples. For the previous examples we will only alter the bandwidth or priority if our original solution altered either.

Example 1

Please refer to Example 2 for delay calculations (for the Example 1 solution above). Now, again let's check if there is a client $c \in \{1,3,6,7,8\}$ such that $D(P'_c) \gt \alpha_c \cdot d(c)$:

$D(P’_1) = 2$

$d(1) \cdot \alpha_1 = 2 \cdot 1$
$2 \leq 2$, accept

$D(P’_3) = 2$

$d(3) \cdot \alpha_3 = 2 \cdot 1.75$
$2 \leq 3.5$, accept

$D(P’_6) = 4$

$d(6) \cdot \alpha_6 = 3 \cdot 1$
$4 > 3$, reject

$D(P’_7) = 4$

$d(7) \cdot \alpha_7 = 4 \cdot 1$
$4 \leq 4$, accept

$D(P’_8) = 5$

$d(8) \cdot \alpha_8 = 3 \cdot 1$
$5 > 3$, reject

Since customers have complained we make no money. So, total revenue $ = \$0$ (recall we did not change the bandwidths so our overall revenue does not go below zero).

Example 2

For the delay calculations, please see Example 2. Now, again let's check if there is a client $c \in \{1,3,6,7,8\}$ such that $D(P'_c) \ge \alpha_c \cdot d(c)$:

$D(P’_1) = 2$

$d(1) \cdot \alpha_1 = 2 \cdot 1$
$2 \leq 2$, accept

$D(P’_3) = 4$

$d(3) \cdot \alpha_3 = 2 \cdot 1.75$
$4 > 3.5$, reject

$D(P’_6) = 4$

$d(6) \cdot \alpha_6 = 3 \cdot 1$
$4 > 3$, reject

$D(P’_7) = 4$

$d(7) \cdot \alpha_7 = 4 \cdot 1$
$4 \leq 4$, accept

$D(P’_8) = 3$

$d(8) \cdot \alpha_8 = 3 \cdot 1$
$3 \leq 3$, accept

Since at least one customer has complained we make no money. So,total revenue $ = \$0$ (recall we did not change the bandwidths so our overall revenue does not go below zero).

Example 3

Please see Example 3 for delay calculations. Since in Example 3 we increased the bandwidth at nodes $3$ and $9$, we propagate that change to here.

For delay calculation, please see Example 3. Now, again let's check if there is a client $c \in \{1,3,6,7,8\}$ such that $D(P'_c) \gt \alpha_c \cdot d(c)$:

$D(P’_1) = 2$

$d(1) \cdot \alpha_1 = 2 \cdot 1$
$2 \leq 2$, accept

$D(P’_3) = 4$

$d(3) \cdot \alpha_3 = 2 \cdot 1.75$
$4 > 3.5$, reject

$D(P’_6) = 3$

$d(6) \cdot \alpha_6 = 3 \cdot 1$
$3 \leq 3$, accept

$D(P’_7) = 4$

$d(7) \cdot \alpha_7 = 4 \cdot 1$
$4 \leq 4$, accept

$D(P’_8) = 3$

$d(8) \cdot \alpha_8 = 4 \cdot 1$
$3 \leq 4$, accept

Since at least one customer has complained we make no money and lose money for increasing bandwidth. So,total revenue $ = \$0 - (2 \cdot \$15) = -\$30$.

Example 4

For delay calculation, please see Example 4. Now, again let's check if there is a client $c \in \{1,3,6,7,8\}$ such that $D(P'_c) \gt \alpha_c \cdot d(c)$:

$D(P’_1) = 2$

$d(1) \cdot \alpha_1 = 2 \cdot 1$
$2 \leq 2$, accept

$D(P’_3) = 4$

$d(3) \cdot \alpha_3 = 2 \cdot 1.75$
$4 > 3.5$, reject

$D(P’_6) = 3$

$d(6) \cdot \alpha_6 = 3 \cdot 1$
$3 \leq 3$, accept

$D(P’_7) = 4$

$d(7) \cdot \alpha_7 = 4 \cdot 1$
$4 \leq 4$, accept

$D(P’_8) = 4$

$d(8) \cdot \alpha_8 = 3 \cdot 1$
$4 > 3$, reject

Since at least one customer has complained we make no money. So,total revenue $ = \$0$ (recall we did not change the bandwidths so our overall revenue does not go below zero).

CSE 331 Project

Acknowledgment

Some Suggestions and Warnings

Form groups of size EXACTLY $3$

Groups should agree on one programming language

The same group for ALL problems

There are no optimal algorithms known!

Start early!

What algorithms techniques will be relevant?

Optimizing the runtime of your code is NOT the main objective

Use the Notation Table

Coding, Reflection and Survey are on different pages

Background

The Basic Problem

The Problem

Simplifications galore!

The Graph

Clients vs. Routers

$d_e=1$ for all edges $e$

Packets are different

One packet per client

Routing is centralized

No bound on incoming traffic

Walkthrough video

Routing of packets

Larger value is higher priority

All packets are sent out of $i$ at the same time

Walkthrough video

Algorithm Idea

Algorithm Details

Payments and Revenue

Clients payments can vary

Example 0

$d(c)$ in the above graph $G$

Show All Problems

Problem 1 [5 points]

The Problem

Input

Penalty

Revenue

Output

Objective

Hint

Walkthrough video

Example 1

A Solution

Justification for claim on revenue

Problem 2 [10 points]

The Problem

Capturing bandwidth by a single number

Perfect knowledge of $\alpha_c$

Input

Note

Penalty

Revenue

Output

Objective

Walkthrough video

Example 2

A Solution

Note

Total Revenue

Determining $D(P')$ for every client

At Time Tick $0$:

At Time Tick $1$:

At Time Tick $2$:

At Time Tick $3$:

At Time Tick $4$:

Determining Penalty and Calculating total revenue

Example 1 solution

Solution to Example 1

Determining $D(P')$ for every client

At Time Tick $0$:

At Time Tick $1$:

At Time Tick $2$:

At Time Tick $3$:

At Time Tick $4$:

At Time Tick $5$:

Determining Penalty and Calculating total revenue

Problem 3 [20 points]

`At Time Tick $0$:`

`At Time Tick $1$:`

`At Time Tick $2$:`

`At Time Tick $3$:`

`At Time Tick $4$:`

`At Time Tick $0$:`

`At Time Tick $1$:`

`At Time Tick $2$:`

`At Time Tick $3$:`

`At Time Tick $4$:`

`At Time Tick $5$:`

`At Time Tick $0$:`

`At Time Tick $1$:`

`At Time Tick $2$:`

`At Time Tick $3$:`

`At Time Tick $4$:`

`At Time Tick $0$:`

`At Time Tick $1$:`

`At Time Tick $2$:`

`At Time Tick $3$:`

`At Time Tick $4$:`