CS6250 Computer Networks
Assignment I – Solutions
1. Policy Routing (20 points)
a) What routes does GT advertise to Cogent, Comcast, Qwest and Internet2?
GT advertises PG to Cogent, Comcast and Internet2. No advertisements to Qwest.
b) Answer question 1 for the case where the link to Cogent is lost.
GT advertises PG to Qwest, Comcast and Internet2.
c) If the connection to Internet2 is lost, under what condition will Georgia Tech be able to send packets to the academic network PI.
Qwest and Cogent provide default routing, which means any packet with destination address GT is specifically unaware of is sent to Qwest. Qwest will be able to route those packets to PI only if Internet2 advertised those addresses to Qwest through some means (either by directly peering with Qwest, or by being a customer of Qwest, or by having sibling relationship with any of Qwest’s peers/customers).
2. BGP Routing (30 points)
When there are no policies,
a) Show the routing table (destination prefix, next hop) of node C4, if we use the default hot-potato routing.
Destination Next Hop
192.1.0.0/22 D5 (nexthop is not C5 according to BGP table and prefixes are usually aggregated)
192.2.3.0/24 D5
b) What is the complete route from node C4 to the network 192.1.0.0/24? Is that the shortest path to that network?
C4-C5-D5-D4-D1-D2-B8-B4-B5-B2-B3: 10 links (Multiple solutions exist)
No, the shortest path is actually through A8 and it has 8 links: C4-C3-C1-A8-A5-A3-B1-B2-B3
c) Show the routing table of node C4, if we use cold-potato routing in all ASes.
We have two AS paths to reach AS200. A8 advertises a MED value of 2 and D5 advertises a MED value of 3. So, next AS is AS100 in this case. And, the next hop to reach AS200 is A8 (and not D5).
Destination Next Hop
192.1.0.0/22 A8
192.1.3.0/24 D5
192.2.3.0/24 D5
d) When there are no policy constraints, what is the next main reason for the Internet path not being the shortest path?
When there are no policies, LocalPref does not exist. Hence, we focus on the next criteria for BGP path selection - AS path length. Shortest AS path does not imply the shortest number of total hops because the number of hops in each AS varies. The AS hides the actual number of hops present inside its administrative domain.
When AS400 becomes strict peer (and not sibling) with AS200 and AS300, it will not provide any transit operation between those two domains. In that case,
e) Show the new routing table for both hot-potato and cold-potato routing.
Both hot-potato and cold-potato has to use A8 as the next hop for AS200.
Destination Next Hop
192.1.0.0/22 A8
192.1.3.0/24 D5
192.2.3.0/24 D5
f) What is the route to the 192.1.3.0/24 network?
C4-C5-D5-D4-D3 (4 links)
3. Multicasting (30 points)
We assume that receivers use IGMP and register with the routers. Hence, in no case will B get a packet.
a) Flooding and delivering the packet to all hosts (including C and D). For this question you need to determine the appropriate TTL value to use. Make sure to explain how you determine this value.
There are two ways TTL can be handled in routers when it receives a packet:
- First subtract 1, and then inspect the TTL, if TTL is ‘0’, do not forward it.
- First inspect the TTL, if greater than ‘0’, then subtract 1 and forward the packet.
We assume the first mode.
The geodesic indicates the length of the shortest path between two nodes in a network. The TTL is calculated as the longest geodesic of the network rooted at the source. The longest shortest path in the given network is 4. Hence, we use the TTL value of 4.
Considering all combinations, we have a total of 26 packet hops.
b) Multi-destination routing where the destination node set is initially set to {C, D, E}.
9 packet hops. (There is duplication of packet at first router)
c) Separately addressed packets to C, D and E.
11 packet hops (Sum of three different end-to-end paths)
d) Reverse Path forwarding.
Similar to flooding, except that the packet is flooded only when it was received over the link that the node would use to get to the source A. Considering that, the number of packet hops used is 15.
(9 proper, 6 discard)
4. DVMRP (20 points)
a) Explain why DVMRP is best suited for dense multicast groups?
In DVMRP, each router by default receives the multicast packet and needs to explicitly send a prune message to stop receiving. This will be wasteful if the number of members per group were less.
b) What is the relationship between DVMRP and distance vector unicast routing? In particular how does DVMRP depend on the available of a distance vector unicast routing protocol?
DVMRP needs a unicast routing protocol to determine the reverse path back to the source. But it specifically relies on a distance vector protocol to elect the designated router. In cases where more than one router is present in a subnetwork, the one which is closer to the source of a multicast message is elected to be in charge of forwarding multicast messages. Knowing the distance of the neighboring node to all possible nodes in the network, helps this election process and thereby we pick the distance vector routing protocol.
c) What is the overhead in multicast routers implementing DVMRP over and above that for unicast routing? Discuss overhead in terms of both message processing and state maintenance requirements.
The router has to maintain the Prune states and the associated timers for each Prune message. In case of leaf routers, it needs to maintain the host IGMP logs to keep track of hosts downstream that belong to a particular group
The extra processing required is to do a RPF check on the source address of the multicast packet. It also has to check its IGMP table to see if there are members for a particular multicast group downstream.