# CSCE 782: Problem Set 2

## Due: Monday, 15 March 2010 @10am

### Selfish Routing

In this problem set you will build a simulation of the Internet routing protocols, extend it with selfish routing agents, and then develop adaptive agents to counteract the selfish ones. The problem has several parts.

### Basic Network Simulation

You will first implement a basic simulation of the routers in the Internet. First you will generate a random undirected graph, making sure that each node in the graph has at least k >= 4 neighbors, thus ensuring that there are multiple paths between every node.

At each time tick you will choose a few nodes at random and each one of these will create a message to be sent. Each message will have `[sender receiver time-to-live]` where the sender and receiver are the who's of the routers (nodes) in question, and the time-to-live is the number of hops left before this message is killed. Assume that all messages start out with a time-to-live of 20.

Each node will implement a highly simplified version of the routing protocol. Namely, every node maintains a routing table with the following columns: receiver, link, #hops. The router updates this table so as to keep track of the minimum number of hops it takes to send a message to receiver via link. The hops are all initially set to a very large value (21). Whenever a node receives a message from sender S coming in on link L and with time-to-live of TTL then that node will update its routing table to show that messages going to S via link L take a maximum of 20 - TTL hops.

At each time tick all nodes will forward the first message in their message queue according to their routing table and will update their routing table as we described. The time-to-live of the message will be decreased by 1 before sending. If it reaches 0 then it will not be forwarded.

This basic implementation of the routing protocol will allow to simulate packets traversing the Internet. If you let it run for a while you will find that the packets arrive at their destination via the shortest possible route. You should plot the time for each message to arrive at its destination, or 20 if it died.

### Selfish Routers

Imagine that these routers actually serve as gateways for ISPs (for example, USC's network). In this case, the nodes only receive a postive utility if when they send a message that originates at that node or when they receice a message that terminates at that node. They receive a negative utility for just passing a message that goes from someone else to someone else (it just uses up their bandwidth and does not benefit their users).

For this second part you will implement a new strategy for a node. The strategy is to no forward any message. Run a graph where one node uses this (selfish) strategy and all the other nodes use the previous (cooperative) strategy. Your tests should quantify how much the average time to destination is increased by having one agent use this strategy.

For the final part of this problem set, you will modify the cooperative agents so that they become adaptive and are able to punish selfish agents. Feel free to use any of the learning techinques we discuss in the book. Your goal is to

1. punish non-cooperative routers and,
2. play nice with other adaptive and cooperative routers.

You want your population of adaptive routers to form an ESS, so that no small set of deviant routers can take advantage your population.

Idea: if a node sends a message and the message dies because its time-to-live reaches 0 then the node updates that the #hops for that `receiver/link` pair to 21.

José M. Vidal