Internet Technologies I, Session 3. IP Extensions.

Internet Technologies I, Session 3 IP Extensions. 13 October 01.

1. Recapitulation

Subnets
- The scheme is extensible (you can introduce many levels of hierarchy, if the structure of your networks makes that a useful thing to do).
- Subnetting is invisible from the outside (a router implementing a subnetting scheme doesn't have to tell "upstream" routers what it's doing, and this reduces the amount of information routers have to keep track of in general).
- Subnetting began as a scheme by which organizations could get more mileage from the classful address blocks that had been allocated to them, but the same principles can be applied to the case of ISPs managing multiple address blocks.
Importance of the idea of encapsulation
- Encapsulation of the virtual in the physical: on each physical network that an IP packet has to cross, that packet must be encapsulated in a locally-appropriate hardware packet (e.g. an ethernet packet on an ethernet network).
- A similar kind of encapsulation happens involving the different layers of the TCP/IP protocol stack (e.g. TCP will turn out to involve a system of packets or "segments", and to move from machine to machine they need to be encapsulated in IP packets).
- Generalize the idea of encapsulation: for packet types X and Y, we can move packets of type Y by encapsulating them in packets of type X. E.g. we might think of encapsulating IP packets in... other IP packets, and in fact this idea turns out to be productive in some contexts.

2. DHCP (Dynamic Host Configuration Protocol)

Resources
- Comer, Internetworking..., Ch. 23.
- T. Lemon, The DHCP Handbook.
DHCP provides on-the-fly host configuration, most notably IP address assignment. It's a reasonably straightforward client/server protocol.
Motivation
- Increasing need for autoconfiguration (to handle mobile devices; to ease administrative burden in a rapidly expanding Internet)
- Address conservation (address space requirements are given by the maximum number of devices operating simultaneously, rather than by the total number of devices)
- Limitations of existing autoconfig protocols (either you don't get enough info or you have to do per-client config)

3. NAT (Network Address Translation)

Resources
- Comer, Internetworking.... Ch. 20, sections 20.6-.
The IETF has reserved (in RFC 1918) a set of address blocks for use on internal networks. These are "private" addresses in the sense that they can't be reached from the public internet (in principle because backbone ("default-free") routers don't carry routes to them). The idea then is that you use these private addresses internally, and translate to valid public addresses at the edge of your network.
Motivations
- Avoid renumbering on ISP transition
- Conserve public address space
- Security (sessions with private address machines can't be initiated from the public Internet)
- NAT offers a way to do these things that's transparent to hosts (i.e., doesn't require host reconfiguration)
Various address mapping functions between public and private address space are possible:
- One-to-one
- Many (internal) to one (or few) (external). There are various possibilities here
  - First come first served
  - Keep a table of internal addresses and external hosts contacted from those internal addresses (we can map multiple internals to a single public address as long as the internals are contacting distinct external hosts)
  - Keep a table of internal addresses and external hosts/ports contacted from the internals (we can map multiple internals to a single public address as long as they're contacting distinct services)
  - Keep a table of internal addresses/ports and external hosts/ports contacted from the internals (we can map multiple internals to a single public address as long as they're coming from distinct ports)
  - As previously, but rewrite the source port in case of conflict (and keep track of this too; we can map multiple internals to a single public address as long as we haven't exhausted the port space)

Marlboro example. We've just opened a new T1 connection to a new ISP (Sovernet) in the last two weeks, and in this transitional phase things are as convoluted as they've ever been. Here's a brief summary:

Marlboro campus academic network. Old: static 12.6.230.x addresses; DHCP (primarily for machines in student dorms) into 10.1.x.x private addresses; NAT of the 10.1 addresses into our public 12.6.230.x address space for outbound internet traffic. New: policy routing of web traffic from 10.1 to Brattleboro and out through Sovernet (NATing in our linux router). We're doing this to take advantage of excess capacity in the new T1.
Marlboro campus administrative network. Old: static 12.6.231.x addresses. New: 10.0.x.x private addresses. Policy routing of all traffic from these addresses to Brattleboro and out through Sovernet (NATing in our linux router).
Gradcenter network. Old: static 12.6.230.x and 12.6.231.x addresses; DHCP into 10.2.0.0 private addresses; NAT of the 10.2 addresses into 12.6.230.x for outbound traffic (i.e., traffic travelling up the T1 either to the Marlboro networks or to get out to the Internet). New: 216.114.150 static addresses (that's the address block we received from Sovernet). Linux router configured to pass 216.114.150 traffic out to Sovernet, and to NAT any 10.x traffic that reaches it into 216.114.150.116-126.

Here's what the NAT setup on the Cisco 3640 looks like (the NAT config on the 2501 is similar):

# set up a pool of 'public' addresses to be used by the NAT box:
# give the pool a name ('nat-pool'); give the range of addresses that defines the
# bounds of the pool; give the netmask those addresses are to interpreted relative
# to (n.b. 'prefix-length 26' is another way of saying 255.255.255.192)
ip nat pool nat-pool 12.6.230.194 12.6.230.204 prefix-length 26
# set up an access list, i.e., a rule governing access to a resource:
# give the access list an identifier ('1'); we want to allow access ('permit');
# and who we want to allow access to is everybody in 10.1.2.x (don't worry about
# the funny looking mask)
access-list 1 permit 10.1.2.0 0.0.0.255
# ok, here we go, set up the NAT:
# the guys on the inside who we're going to let out are the ones specified in
# access list '1'; the pool of public addresses we have to play with is the one
# defined in 'nat-pool'
ip nat inside source list 1 pool nat-pool overload

And here's the NAT config on the linux router

# uses the netfilter facility in the linux 2.4 kernel; we'll be working with
# netfilter next trimester in connection with filtering/firewalls
#
# briefly: if you see a packet from 10.0.0.0/255.252.0.0 (i.e., from our 10.0,
# 10.1, or 10.2 private address blocks) that's trying to get out interface
# hdlc0, NAT it to a 216.114.150 number
#
# more verbosely:
#   "-t nat": netfilter maintains a number of rule tables; we want to add to
#             the nat one
#   "-A POSTROUTING": append this rule to the POSTROUTING rule list (i.e.,
#             the (pre-defined) list of rules that are applied after
#             we've decided where to forward the packet to)
#    "-s 10.0.0.0/14 -o hdlc0": these are our match criteria--we're looking
#             for packets coming from certain addresses and heading out a
#             particular interface
#    "-j SNAT": the particular kind of NAT we want to do is source NAT--we
#             want to mangle the source address (rather than the destination
#             one)
#    "--to 216.114.150.116-216.114.150.126": when you find a packet that meets
#             the match criteria, swap in one of these source addresses
/sbin/iptables -t nat -A POSTROUTING -s 10.0.0.0/14 -o hdlc0 -j SNAT --to 216.114.150.116-216.114.150.126

Complications
- Performance (per packet header rewriting)
- Applications may break (especially if they carry raw IP addresses in the data part of the packet; there are Application Layer Gateways to deal with these problems on a per service basis, but they don't always work perfectly and they certainly add to the performance overhead)
- 1.2.5.3 Session management is tricky (but this presupposes a discussion of TCP)

4. IPsec

Cryptography background
- The idea is that you have some gizmo that will turn plaintext into undecipherable gibberish; that you transmit the encrypted message over the network; that the intended recipient runs the ciphered text back through the gizmo and retrieves the original text.
  
  Of course, if everybody has the same gizmo--and we'll assume that the cryptographic algorithms themselves can't be kept secret--you haven't really gained anything here: if somebody intercepts the encrypted transmission they can just do what the intended recipient does to recover the original. So what we really do is feed the gizmo both the plaintext and a "key", an additional data value. The encrypted output of the gizmo is then a function of both the original message and the key, and the idea is that the recipient needs to know the key to retrieve the original (observe that this variant is really only an improvement on the previous one if the range of possible keys is large--otherwise someone could try them all). In classical ("symmetrical") cryptography, the key is a secret shared by sender and recipient.
  
  Shared secret keys are plausible on a small scale, and where sender and recipient can have "out of channel" (e.g. face-to-face) communication. But things break down in the context of the Internet. You want to have a confidential transaction with somebody in Uzbekistan with whom you've had no prior communication. You worry about the data possibly being intercepted en route--hey, it's the Internet!--so you'd like to encrypt the communication. What to do? Send a secret key by email.. over the Internet?
- Public key cryptography to the rescue. In the last twenty-five years an important new class of cryptographic gizmos has arisen. These work on the basis of a pair of keys--conventionally called "public" and "private"--which have inverse effects: a message encrypted with a public key can only be decrypted with the corresponding private key, and vice versa.
  - The idea is that this is supposed to buy us the possibility of secure and authenticated communication--without shared secrets. You get a key pair. You keep your private key... private. You spray paint your public key on the side of the biggest building in town. Now if somebody wants to communicate securely with you, they encrypt a message with your public key and send it. Doesn't matter if the message is intercepted in transit, because only you, holder of the corresponding private key, can decrypt it.
    
    Similarly if what's crucial in some communication is establishing that a message is coming from you, you can encrypt the message with your private key. If the recipient can successfully decrypt with your public key, he/she/they/it will know the message must be coming from the holder of the corresponding private key.
    
    Of course in this last case we're dealing with authenticity but not confidentiality. Since your public key is... public, if the message is intercepted anybody can decode it. But it's possible to have your cake and eat it too: if you first encode with your private key, and then encode with the recipient's public key you get both authenticity and privacy: only the recipient can decode the doubly-encrypted message that passes over the network; only you could have sent what lies within.
  - Now let's introduce a couple additional concepts, so we can approximate current practice. First, "digital signature". To begin with, there's a notion of a "message digest", which is a compressed binary representation of a message (basically you take a message and boil it down to a small, fixed-length string of bits; the digest is used to verify the integrity of a message--that the message-as-received is the same as the message-as-sent--so the closest analogy to this in what you've previously seen is the "checksum" in a packet header). There are some standard algorithms for producing digests, but in the diagram below I've just got a black box labelled "digestifier". To add a "digital signature" to a message you do the following:
    - Take the message and make a digest of it
    - Encrypt the digest with your private key; the result is a "digital signature"
    - Send both the original message and the encrypted digest/"digital signature"
    And then at the other end the recipient:
  - Takes the message and makes a digest of it
  - Decrypts your digital signature, using your public key (revealing the digest)
  - Compares the newly computed digest with the one in your signature. If they're the same, (a) the message was received intact; (b) you sent it
- Now, "digital certificates". Er, we have a problem. When we decrypt with a public key, we know that the message must've been created with the corresponding private key, but we don't really know the person associated with that key is who we think it is.
  
  What we'd like is certification by some authority (a Certificate Authority or CA); the CA vouches for the fact that some person is truly the owner of some key (presumably having done something to establish this). It does so by issuing a "digital certificate" which contains the key, the name of its owner, some other information, and... the CA's own digital signature.
  
  So, you
  - Receive an encrypted message, putatively from some individual
  - Contact a CA and fetch that person's digital certificate
  - Process the certificate as in the discussion of "digital signatures" above (of course to do that we're going to need the CA's public key--and need to be sure the key really belongs to the CA; which means that we're going to need the CA's certificate, which is signed by whom? Well, typically the CA itself--not very satisfactory, but it's either that or infinite regress).
  - If everything checks out, use the public key contained in the certificate to decrypt the message you received
- One disadvantage of public key algorithms is that they're computationally expensive--much more so than symmetric cryptographic algorithms. One common technique is to use public key cryptography at the outset of a conversation to negotiate a shared secret, a symmetric key that can then be used for bulk encryption over the remainder of the interaction. There's even a way to do this, known as Diffie-Hellman key exchange, when you're starting from scratch (i.e., when no public/private key pairs are available):
  - Alice picks two primes n [e.g. 47] and g [3] and shouts them out to Bob
  - Alice picks (secret) x [8], Bob picks (secret) y [10]
  - Alice sends Bob g**x mod n [28]
  - Bob sends Alice g**y mod n [17]
  - Alice computes ((g**y mod n)**x) mod n [4]
  - Bob computes ((g**x mod n)**y) mod n [4]
  - They're the same number! (= g**(xy) mod n)
  - Evil hears Alice shout to Bob (knows g and n). Let's say Evil intercepts the g**x mod n message. Evil now knows g = 3, n = 47, and that g**x mod n = 28. Evil can brute force a solution given these ridiculously small values for g and n, but not for large ones.

IPsec resources

Comer, Internetworking..., Ch. 32, sections 32.5-32.11.
IETF IPsec Working Group (see especially RFCs 2401-2412).
N. Doraswamy and D. Harkins, Ipsec: The New Security Standard. Prentice Hall. 1999. 0130118982.
Timestep/Alcatel, Understanding the IPsec protocol suite

IPsec offers "network"- (i.e., IP-) level security

Security mechanisms can be implemented at different layers of the network stack. They can be built into individual applications. They can be built into a software layer that provides services to applications (e.g. SSL/TLS). They can be built into specific physical networking technologies (various forms of "link-layer" encryption). The shortcoming of these schemes is that they're not general. The fact that you do PGP encryption of your mail provides no protection for your other communications. Or put from the perspective of the programmer or network admin, leaving security as an application-level function means that security mechanisms have to be built into each application separately.
IP-layer security, on the other hand, is universal. No matter what applications are involved, no matter whether those applications use TCP or UDP (or anything else), no matter what physical network systems you have to cross, everything has to go through the IP layer on each device a packet encounters.
One consequence of this generality is that you get a great deal of flexibility in configure IPsec topologies. You can have an IPsec-grounded connection between two (IPsec-aware) endpoints. On the other hand you could have an IPsec-grounded connection between two intermediate systems--e.g. between two edge routers, in a typical LAN-to-LAN VPN scenario. In this case notice that the end systems may know nothing at all about IPsec.
Limitations. IP-level security is an important concept, but it may not serve all your security needs. Notice that in the router-to-router case above, we haven't provided any security on the LANs behind the two routers. Even in the end-system to end-system scenario there are limits imposed by the very nature of IP. Recall that IP is about identifying machines and delivering data between them. It has, however, for example, no notion of a "user". IPsec tries to authenticate IP systems and devliver data between them securely, but it has no notion of user authentication, and applications may have to deal with this issue separately

IPsec is a set of complex IETF standards. It's compatible with IPv4, and is a mandatory component of IPv6. IPsec is already a standard piece of many shipping operating systems: Windows 2000, Solaris 8, Mac OS X, Cisco IOS. It doesn't yet come as part of core Linux, largely for political/legal reasons, but later on we'll be looking at freeswan, which adds IPsec functionality to the Linux kernel. In addition, an increasing number of third-party applications use IPsec, e.g. PGPnet and SSH Sentinel. Interoperability among different IPsec implementations is still an issue at this point. Some vendors offer hardware support for IPsec.

IPsec provides confidentiality, integrity, authentication. It offers them in different combinations: you can do authentication/integrity alone, or you can do them in combination with encryption. And for any given service you typically get a choice of algorithms.

IPsec has three main components: AH--Authentication Header--provides authentication and integrity. ESP--Encapsulating Security Payload--does authentication, integrity, encryption. IKE (Internet Key Exchange) is a negotiating protocol: we use it to determine whether we're going to do AH or ESP or both, and which particular AH and ESP algorithms and keys we'll be using. AH and ESP correspond to distinctive packet formats. For each, there are two forms, corresponding to the two modes in which IPsec runs, namely transport and tunnel. IKE on the other hand is a network protocol: IKE entities listen at UDP/500.
AH (transport mode)
- AH involves inserting a new header between the IP header and payload.
  Regular:
  
  AH:
- AH format
```
next header [1 byte]
payload length [1]
reserved [2]
spi [4]
sequence number [4]
authentication data []
    
```
  - next header: In a plain IP packet, the "protocol" field in the IP header indicates what's being carried in the packet--whether what follows the header is TCP, UDP, whatever. But now we're inserting an AH header right after the IP one. The "protocol" field in the IP header now gets the value 51, reserved for AH, and the AH header has a "next header" field that says what comes after it--i.e., it'll have the value of the "protocol" field in the original IP header
  - payload length: how long is the AH (in longs - 2)
  - reserved: think up a good use for these two bytes
  - IPsec has a concept of a Security Association (SA). An SA describes a particular negotiated IPsec contract--the algorithms and keys in use, and so on. The full SA isn't carried in each packet, but an identifier for it, mutually agreed on both the parties to the contract and referred to as the "security paramter index" (SPI), is.
  - sequence number: increments from 0 for each SA.
  - authentication data: authentication involves a keyed hash of the payload of the original packet, typically using one of the usual suspects, SHA-1 or MD5. "Keyed" hash means that the input to the hash function consists of a key agreed upon by sender and recipient (we want to authenticate the origin of the message) as well as the packet data (we want to assure the integrity of the data as received). Authenticity might, alternatively, have been established by private key signing, but remember that private key operations are computationally expensive, and that we're talking about a per packet operation.
ESP (transport mode)
- An ESP packet has many of the same components as an AH one, though their ordering differs and though the structure--reflecting the additional encrypting step--is more complicated. ESP involves the same kind of "header chaining" that goes on in AH--the "protocol" field in the IP header has the ESP-indicating value 50, and the ESP matter includes a "next header" field that indicates the contents of the original datagram.
- To a first approximation, what happens is that you strip off the payload from the original packet, encrypt it, tack on an ESP header, and authenticate the whole bundle. More exactly:
  
  ...where the ESP header consists of an SPI and sequence number (same significance as in AH), and where the ESP trailer consists of:
  - a variable amount of padding (up to 255 bytes; to match the block size an encryption cipher wants and possibly to mislead eavesdroppers as to the amount of data being transmitted);
  - a byte indicating the amount of padding;
  - ...and a "next header" byte
"Mutable fields". One difference between AH- and ESP-style authentication is that in AH, the hashed data includes the original IP header as well as the packet payload. Or more exactly, it includes the header excepting the so-called mutable fields (we don't want to insist on the integrity of things we know will change, e.g., the time-to-live field). ESP authentication doesn't include any IP header values. Notice that, since under AH the source and destination IP addresses must remain constant, it's impossible to do NAT between AH partners (in either transport or tunnel mode).
Transport mode, as above, is most easily thought of as a technique for direct, endpoint-to-endpoint IPsec communication. But we've seen that IPsec can be used in other topologies. Tunnel mode is intended for gateway-to-gateway communication. The idea here is that an endpoint--say an IPsec-unaware one--behind one gateway can communicate with an endpoint behind the other gateway with IPsec protection in place between the two gateways: the sender sends; the local gateway encapsulates the entire original packet in a whole new one, addressed to the remote gateway; the remote gateway decapsulates the original packet and sends it on its way. Here's how this plays out in detail for AH and ESP
- AH (tunnel)
  
  ...where the authentication header has the same form as under transport mode
- ESP (tunnel)
  
  ...where the ESP header and trailer have the same form as under transport mode
- Observe that tunnel and transport mode have different security characteristics: since, in tunnel mode, the only IP addresses that are visible belong to the two gateways, it's harder to do "traffic analysis" than in the case of transport mode. An eavesdropper could see that packets were passing between the two gateways, but would have no idea what the actual originating and terminating IP addresses were
IKE
- AH and ESP describe what things should look like once an agreement about algorithms, keys, etc. are in place, but they say nothing about how to get to that point. IKE handles all the setup work.
- The main services it provides are (a) endpoint authentication (it'd be nice to know who we're talking to); (b) algorithm negotiation; (c) key generation and exchange. In general it offers IPsec participants negotiating latitude: different forms of authentication are defined (public key, preshared secret...); all implementations are required to support certain basic hash and encryption algorithms, but you're free to negotiate for other ones. Key exchange is based on Diffie-Hellman.
- IKE setup occurs in the following two phases:
  - Phase 1. Negotiate an "IKE SA" = set up a basic encrypted channel between two IPsec participants, through which we can negotiate further SAs. There are different ways of generating the IKE SA, and the exact sequence depends among other things on the style of authentication we're using, but here's, schematically, how "Main mode" works. There are three pairs of exchanges:
    - Agree on algorithms. One side sends the other a set of "proposals". The recipient picks a set it likes and sends it back.
    - Exchange Diffie-Hellman values (g**x mod p...) and matter for verifying identity (e.g. "challenges" or "nonces"). After this exchange the two sides can compute the Diffie-Hellman shared secret; from this they then derive session keys.
    - Verify identity (e.g. take the challenge value sent by the other side in the previous exchange, hash it, encrypt it with your private key and send it back)
  - Phase 2. With the IKE SA in place, the two sides can proceed to negotiate one or more specific IPsec SAs. This can be as simple a process as an initiator sending a set of proposals and a responder returning its selection.

5. Multicast (!= multimedia, but multimedia is a potential application for multicast)

Resources
- Comer, Internetworking..., Ch. 17.
- Thomas Maufer, Deploying IP Multicast in the Enterprise.
- Beau Williamson, Developing IP Multicast Networks.
- IP Multicast Initiative (www.ipmulticast.com)
- Cisco multicast pages (ftp://ftpeng.cisco.com/ipmulticast.html)
- Henning Schulzrinne's multicast references (http://www.cs.columbia.edu/~hgs/internet/multicast.html)
The general motivation is: how to do multipoint delivery efficiently (efficiently with respect to bandwidth, endpoint resources)
Historical context: Ethernet provided multicast support in hardware from the beginning (mid '70s). IP multicast comes much later (late '80s). Commerical applications are increasingly becoming multicast-aware, much work is being done on the further development of multicast-related protocols, production-grade multicast router software is widely available, but we still don't have general deployment of multicast routing in the Internet.
Hardware multicast (example of ethernet)
- Addressing modes: unicast (one recipient), broadcast (all recipients), multicast (some recipients).
- The broadcast address is predefined (ff:ff:ff:ff:ff:ff). Unicast addresses are typically 'burned into' network hardware. Multicast addresses (a) take a particular form (the lowest bit of the highest byte is on); and (b) are configurable--a host, wanting to receive certain transmissions, gives itself one or more multicast addresses (i.e., tells the network hardware to accept packets sent to those destinations).
- So what exactly is the advantage of multicast over broadcast? The network hardware acts as a filter. It passes packets sent to destinations it's been configured to accept up to the OS for handling, others it rejects. The network hardware in every device sees every broadcast packet and must hand each one up to the OS (to the device driver). The network hardware in every device likewise sees every multicast packet, but only retains those sent to addresses it's been configured to accept. The result is that the OS only has to deal with packets we have reason to think it's actually interested in.
IP multicast
- Addressing modes: unicast, broadcast, multicast.
- The broadcast address is predefined (all 1s for local broadcast, all 1s in the host component for network-directed broadcast). Unicast addresses, appropriate in terms of a machine's position in the overall network topology, are assigned by some (static or dynamic) mechanism. Multicast addresses (a) take a particular form (224.x.x.x-239.x.x.x; a leading four bits (1110) followed by a 28-bit group identifier; some addresses in the 224-239 block--e.g. 224.0.0.x and 239.x.x.x are reserved for special purposes); and (b) are configurable--a host, wanting to receive certain transmissions, gives itself an IP multicast address (i.e. (1) tells the network hardware to accept packets sent to a certain hardware multicast destination, algorithmically transformed from the IP multicast address; and (2) tells a local router it wants to receive transmissions sent to the IP multicast address).
- The fact that n hosts may join a multicast group means that multicast must used UDP rather than TCP (which inherently involves connections between pairs of endpoints). Since UDP doesn't offer guaranteed delivery, this means that reliable multicast is... problematic. This is an area of active research, but at this point reliable multicast, as they say, mainly runs on Powerpoint.
- The fact that the n hosts belong to a multicast group may reside on n networks means that delivering transmissions to all group members is fun. It's all the more fun because anybody can transmit to the group, group member or not. This means that IP multicast is supposed to be able to handle (a) group members subscribing and unsubscribing dynamically, from arbitrary locations on the Internet; (b) data sources for the group appearing and disappearing dynamically, at arbitrary locations on the Internet. These are not trivial requirements! What's interesting is that the burden of satisfying them falls almost entirely on the routing infrastructure.
- Host perspective
  - Sender: just sends to the IP multicast group address (what could be simpler?)
  - Recipient (group member)
    - Tells NIC to accept packets sent to the hardware multicast address 01:00:5e + low 23 bits of IP multicast group identifier (observe this involves multiplexing 32 (28-bit long) IP multicast identifiers onto a single hardware address).
    - Informs router--via the IGMP protocol--of its interest in the IP multicast group. The router then contrives to get all traffic for the group forwarded to it, and it then hardware multicasts the traffic onto the network to which the interested host is attached.
  - IGMP is specifically for host-router exchange of multicast group membership information
    - The basic scenario is: host sends a join ('membership-report') message; router then periodically polls ('general-query') to see what groups are still populated, to which hosts respond with further 'membership-report' messages; ultimately host sends a 'leave'
    - IGMP involves a number of bandwidth optimizations (e.g. all IGMP traffic is itself multicast)
    - IGMP has been steadily evolving: v2 introduced explicit leave messages (thus reducing "leave latency"); v3 introduces the notion of source-specific joins and leaves (giving recipients finer-grained control over what data streams they receive).
- Router
  - To deliver multicast data, routers need to build one or more distribution trees. There are essentially two models for doing this: one is to build a tree for each source (i.e., for each device sending to the multicast group); the other is to build a single tree, and have all the sources send through it.
  - Source-trees (basis for so-called dense-mode protocols)
    - In conventional unicast routing, the net-identifying prefix on a destination IP address is used to forward a packet towards a particular network, a particular point in the overall network topology. In multicast, we can't just use the destination address because the destinations are everywhere. Instead we make the highly counter-intuitive move of forwarding based on the source on where the packet came from. Essentially there are two general models for doing this.
    - Starting from some source, try to get the data stream everywhere (i.e., onto all networks), but do this in such a way that any given link is only traversed once.
    - So, the source starts sending. The first-hop router sends the stream out all its ports. All subsequent routers do "reverse path forwarding" (RPF): for a given packet, accept it only if it arrives on the interface that the regular unicast routing table says is the shortest way back to the source; if the packet is accepted, send it out all the other ports.
    - This lets us reach all destination networks, but it's not a good idea to broadcast to the Internet indiscriminately, so we start cutting back the tree: edge routers with no attached group members send prune messages upstream; upstream routers stop sending to them; prunes can percolate upstream, and larger branches get cut off the distribution tree.
    - There's a complement to prunes, grafts: a router can ask an upstream router to be reconnected to a tree (e.g. if it acquires a new group member). "Prune state" is also periodically--typically every couple minutes--forgotten, and we go through the whole cycle again, starting with the flooding.
    - We get one of these distribution trees per source (and a multicast group may have many). This means that a tremendous amount of state information has to be maintained, in every router. Routers that are actually in distribution trees will have multicast routing table entries of the form:
```
(source,group)  (list-of-interfaces-to-forward-to)
        
```
      Even routers that aren't in any current distribution trees need to maintain prune state so they can honor graft requests.
    - A number of protocols fit this paradigm: DVMRP, PIM-DM...
  - Shared trees (basis for so-called sparse-mode protocols)
    - Here the idea is, first, to maintain a single distribution tree per group, and second, not to do any flooding, to only send data where it's been explicitly requested.
    - Designate a core router or "rendezvous point" (RP).
    - When a host joins a group via IGMP, the router nearest it sends a join towards the RP. Forwarding state is created in each router the request transits 'til the request reaches a router already in the shared tree.
    - Data for the multicast group goes from the router closest to the source to the RP, encapsulated in regular IP. The RP then starts sending the data down the distribution tree.
    - Pros: no broadcast, fewer trees, less state.
    - Cons: suboptimal paths; RP placement turns out to be tricky; RP as single point of failure.
- Multicasting and switched LANs
  - The original forms of ethernet involved a shared bus. Switching, among other benefits, offered higher effective bandwidth by reducing the possibility for collisions.
  - Switching fever: if switches reduce collisions, and if I'd been previously segmenting my network with routers to limit the collision rate, I can throw away all my routers and drop in (cheaper, faster) switches.
  - However switches can't constrain all traffic. Broadcast needs to go out all ports. Multicast, it turns out, similarly (think about it in terms of how a switch builds its address x port table--it does associations between source addresses and ports; but a multicast address is always a destination address, never a source one). There are a couple of techniques for dealing with this situation:
    - IGMP spoofing. Have the switch listen for multicast traffic. If it sees an IGMP membership report, build a table entry associating the hardware multicast address of the group being reported on with the port the report arrived on (to the exclusion of all other ports, unless similar IGMP reports arrive on them too). Special handling of IGMP traffic is necessary to make this work. The address table also needs to be able to hold multiple ports per address. And good hardware support is required, or the requirement of inspecting all multicast traffic will kill your switch.
    - CGMP. This is a proprietary Cisco protocol that involves cooperation between a router and a switch. Here the switch does no special handling of multicast packets. The router processes IGMP packets in the normal way, except it now copies information back to the switch--for example it might say "The guy at 00:80:00:a2:87:72 just joined multicast group 01:00:5e:00:01:01". The switch then looks up 00:80:00:a2:87:72 in its table see that it's associated with a given port, and builds a new entry associating that port with 01:00:5e:00:01:01.

IT Home