We saw how BGP routing can be formulated as a game where the selfish players are autonomous systems (ASes), and we saw a case where this game has no Nash equilibrium (stable state). That is, the control plane will keep switching routes even though the physical network is stable. In this problem, we'll see an example where there are two equilibria, and different sequences of events could lead to one or the other. Consider the network below: provider customer 2 provider peer link customer provider customer destination For simplicity, assume AS 1 is the only destination: it is the only AS that will originate an announcement message. The ASes have provider/customer/peer business relationships as shown. They follow the common route selection and export policies... except that AS 1 is using AS 2 as a backup provider. This means AS 1 has instructed AS 2 to route to AS 1 via the link 21 only when no other path is available. (Incidentally, this is possible with BGP's community attribute.) The effect is that AS 2 prefers to route through AS 3 in order to reach AS 1. Assume that at time 0, no routes have been announced by anyone. Shortly after time 0, AS 1 will begin announcing its IP prefix. (a) Describe a sequence of events (BGP announcement messages and path selection decisions) that lead to one stable state. (b) Describe a different sequence of events that lead to a different stable state. (c) Suppose the network is now stabilized in state (a). A link fails; the BGP routers re- converge; the link recovers; BGP reconverges again; but now the network is in state (b) instead of state (a)! What sequence of events causes this story to happen? That is, which link failed, and which messages get sent?