Transcript 10 pts - ECSE - Rensselaer Polytechnic Institute

ECSE-6600: Internet Protocols
Exam 2 - SOLUTIONS
Time: 75 min (strictly enforced)
[Hint: spend time roughly in proportion to the points allocated
to questions]
Points: 40
YOUR NAME:
Be brief, but DO NOT omit necessary detail
{Note: Simply copying text directly from the slides or notes will not earn
(partial) credit. Brief, clear and consistent explanation will.}
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
1
[10 pts] 1. Intra-Domain Routing Protocols: Explain the similarities/differences
between OSPF and PNNI (5 pts). How does MPLS facilitate traffic engineering
beyond what OSPF or PNNI provide (5 pts)? [Reminder: be brief! You have to
answer many questions in limited time.]
Similarities between PNNI and OSPF – Link state routing protocols, scalable to large
network sizes, support hierarchical routing, and support QoS.
Differences – PNNI uses source routing and mechanisms such as crank back upon route
failures, whereas OSPF does not. This allows PNNI to support tunneling better than
OSPF. OSPF is generally used over connectionless network layer protocols, whereas
PNNI is used in ATM networks where signaling is used to establish connections.
PNNI guarantees better QoS due to the use of signaling in addition to source routing.
MPLS provides the abstraction of transparent tunneling based on explicit source routed
circuits. The choice of the route is decoupled from the problem of traffic mapping
onto the route providing greater flexibility. Global Ids (IP addresses) are mapped to
local ids or labels, which are short and very few in number making switching
decisions fast. Network utility is considered a part of route setup providing for traffic
engineering, above and beyond QoS routing.
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
2
[10 pts] 2. Inter-Domain Routing Protocols: Explain why path-vector & attribute-based
vectoring is preferred to link-state routing in Inter-domain routing (4 pts)? What mechanisms
are used in BGP (and how are they used) to facilitate in-bound and out-bound traffic
engineering for an AS (6 pts).
Inter-domain routing has a different set of requirements – (a) Reachability rather than
optimal routes, (b) Scalability, to support the size of the internet, (c) There is a need
to aggregate addresses to minimize core routing table sizes and associated control
traffic, and (d) Need to support policy based routing.
Link state routing is difficult to employ given the lack of information (hidden link
states) and trust across AS’s. Also it suffers from scalability and privacy issues.
Therefore the path-vector and attribute-based vectoring is preferred to link state
routing.
BGP allows for exchange of reachability information across AS and facilitates policy
based routing. The various load balancing knobs to facilitate in-bound and outbound traffic engineering include :
Local Pref. – controls outbound traffic by preferring one exit path over another.
AS prepending – To reduce inbound traffic, AS path length is artificially inflated.
MED – Indicates receiver preference to control the inbound traffic
CIDR subverting – Advertise different length prefixes for the same set of addresses to
provide load balancing in inbound traffic.
Inbound control knobs may lead to varying degrees of success compared to outbound
knobs.
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
3
[10 pts] 3. Congestion Control: Explain how methods like AQM schemes (eg: RED),
multi-bit feedback (eg: ERICA, VCP) and FEC integration (LT-TCP) improve
performance of transport protocols (6 pts)? What is the concept of TCP friendliness
(2 pts)? How do the binomial schemes allow a family of schemes to be TCP friendly
(2 pts)?
AQM (RED) schemes send early signals of congestion to sources by marking/dropping
packets randomly to avoid congestion and lead to good overall performance.
Multibit feedback schemes allow fine grained control of the operating point in the
network by explicitly providing the senders with rates they should send traffic at.
FEC integration provides robust error recovery and reduces the need for
retransmissions over lossy wireless links. Together these schemes achieve high
throughput and low delay, and also allow for bursty traffic patterns.
TCP friendly congestion control scheme should not take more than its fair share of the
link when operating together with other flows which use TCP. It should be fair to
TCP, match its long term performance and should have the same utility functions.
These properties are desirable in order for new CC schemes to co-exist with TCP.
Binomial congestion control schemes use parameters k, l to increment/decrement their
window size. Such schemes are TCP friendly if k + l = 1. Basically they react
similarly to the lack or presence of congestion by reducing or increasing the
congestion window size in a similar (aggressive) manner. If k + l = 1, then the rate is
proportional to 1/sqrt(p) which is inline with TCP’s performance, and also results in
equivalent utility functions.
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
4
[10 pts] 4. Multicast: Why is the multicast transport reliability problem is very different
from unicast reliability (3 pts)? How are mechanisms like subcast, FEC, feedback
aggregation useful (2 pts)? Explain the drop-to-zero and TCP-friendliness problems
in single-rate multicast congestion control (3 pts). How does RLM achieve multirate multicast congestion control (2 pts)?
Multicast transport reliability is different because – (a) Senders can not keep state
information for a number of receivers. Also the receivers can join or leave
dynamically. (b) Algorithms like TCP which use path properties like RTT estimation
don’t generalize to trees. (c) There are other issues such as (N)ACK implosions and
exposures. (d) Retransmissions need to be filtered.
Subcast – send retransmissions only to a selected group of receivers. This addresses the
exposure issue. FEC uses forward error correction schemes and thus avoids (N)ACK
implosions. Feedback aggregation at routers also avoids the flooding of sender with
a large number of (N)ACKs.
Drop to zero – In single-rate multicast sessions, if every packet loss is considered to be a
signal of congestion, the congestion window (and the throughput) would quickly
drop to 0. Note that a packet can get lost along multiple paths to receivers, leading to
multiple packet losses corresponding to one packet sent. There is a need to be TCP
friendly and not take too much bandwidth, however at the same time do not over
react to packet losses.
RLM provides multi-rate multicast CC using a prioritized set of multicast groups.
Receivers subscribe to max group with minimum drops. It is receiver driven and
adaptive to available capacity. Receivers may subscribe to higher layers or drop a
layer as needed.
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
5
[10 pts] 5. IPv6: How does IPv6 use its abundance of address space to simplify/consolidate autoconfiguration, renumbering, address allocation, neighbor discovery etc (6 pts)? How does the
dual-stack and 6-to-4 automatic tunneling approaches help deal with the transition issues (4
pts)?
A)
IPv6 auto-configuration allows for plug-and-play as the host can use its MAC address as the
host portion of its IPv6 address. In stateless auto-configuration, for the network prefix, the host
multicasts requests to All routers on the link. If no router present, the host uses link-local
address, else it uses the prefix provided by the router. In stateful configuration, to prevent
everyone from connecting, the router asks the host to multicast to All DHCP servers to get an
IP address.
Host renumbering occurs when the prefix changes due to a change in subnet (provider)
address. Hosts learn about prefix changes through router advertisements. Router renumbering
protocol allows domain-interior routers to learn of prefix introduction/withdrawal.
ICMPv6 allows for neighbor discovery by combining features from ARP and Router discovery
(also ICMP, IGMP). A source maintains various levels of caches for destinations, prefixes,
routers and neighbors.
Dual stack allows for indefinite coexistence of both IPv4 and v6. Allows for gradual upgrade to
IPv6 on an application-by-application basis. It allows the applications to choose between v4
and v6. However it requires applications to be able to talk to both IPv6 and v4. Requires name
lookup before connection establishment. It is an application level mechanism.
6-to-4 auto tunneling sends IPv6 packets over IPv4 tunnels. 6-to-4 allows stateless auto-tunnels
establishment where the IPv4 address is used as the IPv6 site address. It is more transparent to
the applications. It requires tunnel end points to be dual stack and requires some manual
configuration of IPv4 addresses. Additional processing is also required at tunnel end points.
Enables auto tunneling on packet by packet basis.
Shivkumar Kalyanaraman
Rensselaer Polytechnic Institute
6