Thursday, April 12, 2012

Part IV: Internetworking Using TCP/IP


Chapter 20: Internetworking Concepts, Architecture and Protocols
  • The motivation for internetworking:
    • No single networking technology is best for all needs
  • Universal Service
    • A communications system that supplies universal service allows arbitrary pairs of computers to communicate
    • Although universal service is highly desirable, incompatibilities among network hardware, frames, and addresses prevent a bridged network from including arbitrary technologies
  • Internetworking
    • Physical network connection with routers
      • An internet router is a special-purpose hardware system dedicated to the task of interconnecting networks.
        • It can interconnect networks that use different technologies such as media, physical addressing schemes, or frame formats.
    • Internet architecture
      • An internet consists of a set of networks interconnected by routers. 
      • The internet scheme allows each organization to select the number and type of networks, the number of routers to use to interconnect them and the exact interconnection topology.
        • To build in redundancy and reduce traffic congestion, organizations typically use multiple routers.
      • The internet is a virtual network because the communication system is an abstraction, that provides the illusion of a uniform network.
  • Protocols for internetworking
    • TCP/IP Internet Protocols stand out as the most widely used
      • Layer 3 (Internet) uses the IP protocol
      • Layer 4 (Transport) uses the TCP protocol

Chapter 21: IP Internet Addressing
  •  Addresses for the virtual internet
    • To provide uniform addressing in the Internet, IP defines an abstract addressing scheme that assigns each host a unique protocol address
      • Applications use IP addresses to communicate
  • The IP  Addressing Scheme
    • An internet address (IP address) is a unique 32-bit binary number assigned to a host and used for all communication with the host.
    • IP Address hierarchy
      • Each computer is assigned a unique address
      • Although network number assignments must be coordinated globally, suffixes can be assigned locally without global coordination.
    • Original Classes of IP Addresses (Superceded by newer format)
      •  The original IP addressing scheme divided addresses into classes
        • Classes differed by the number of 8-bit segments alllocated to the prefix and suffix that together comprise the 32-bit  IP address
          • Class A: one bit identifier (0), 7-bit prefix, 24-bit suffix
            • Accommodates 128 networks; 16,777,216 hosts per network
          • Class B: two bit identifier (10), 14-bit prefix, 16-bit suffix 
            • Accommodates 16,384 networks; 65,536 hosts per network
          • Class C: three bit identifier (110), 21-bit prefix, 8-bit suffix
            • Accommodates 2,097,152 networks; 256 hosts per network
          • Class D: four bit identifier (1110), 28-bit multicast address
            • Class D addresses are still used for multicasting, but multicasting does not work globally
          • Class E: four bit identifier (1111), 28-bit address
            • Class E was reserved and not assigned.
    • Dotted Decimal Notation
        • A syntactic form that IP software uses to express 32-bit binary values when interacting with humans.
          • Represents each octet in decimal and uses dots to separate octets.
    • Authority for Addresses
        • Internet Corporation for Assigned Names and Numbers (ICANN) handles address assignment and adjudication disputes.
          • Does not assign individual prefixes, authorizes a set of registrars to do so.
    • Subnet and Classless Addressing
      • Original "classful" addressing scheme became a limitation to growth
        • Organizations demanded Class A or B addresses to accommodate future growth, meanwhile few group wanted the remaining Class C addresses.
      • Two new mechanisms invented to overcome the limitation:
        • Classless addressing
          • Instead of having distinct address classes, they allowed the division between prefix and suffix to occur on an arbitrary bit boundary
            • For example: an ISP might assign a prefix that is 26-bits long with a six-bit suffix, permitting up to 62 hosts on the prefix
              • This effectively splits Class C addresses into four longer prefixes (with the addition of two prefix bits)
        • Subnet addressing
          • To mark the exact boundary between network prefix and host suffix, a 32-bit value known as an address mask was used.
            • The address mask consisted of 1s marking the places of the prefix bits, and 0s marking the places of the suffix bits
            • Routers would join the IP and address mask using a logical AND function to derive the accurate network prefix.
    • Classless Inter-Domain Routing (CIDR) Notation
      • Specifies addressing and forwarding in a format that is more readable to humans by extending Dotted Decimal notation with a slash followed by the number of prefix bits
        • For example, a 26-bit prefixed network with IP 192.5.48.69 would be: 192.5.48.69/26
    • Special IP Addresses
      • A network address is denoted by host address zero
        • 128.211.0.16/28 is a network because all bits beyond the 28th are zero.
      • Directed Broadcast Address
        • Used to send a copy of a packet to all hosts on a physical network
        • Formed by adding a suffix that consists of all 1s to the network prefix
          • 128.211.0.31/28 is a directed broadcast address
      • Limited Broadcast Address
        • Broadcast on a directly-connected network, used during system startup by a computer that does not yet know the network number.
        • IP address for limited broadcast consists of 32 1-bits
          • 255.255.255.255
      • This Computer Address
        • Used on startup since startup protocols use IP to communicate, but the computer does not yet have an IP
        • All zeros (0.0.0.0)
      •  Loopback Address
        • Used to test network applications during debugging
        • 127/8 reserved for use with loopback
          • 127.0.0.1 is the most popular loopback address
    • Routers and the IP Addressing Principle
      • An IP address does not identify a specific computer. Instead, each IP address identifies a connection between a computer and a network.
      • A computer with multiple network connections (e.g., a router) must be assigned one IP address for each connection.
        • These computers are said to be "multi-homed"

Chapter 22: Datagram Forwarding
  •  Virtual Packets
    • Since it includes incompatible networks, the Internet cannot adopt a particular hardware packet format. 
    • To accommodate heterogeneity, the Internet Protocol defines a hardware-independent packet format
  • IP Datagram
    • Each packet sent across TCP/IP internet is called an IP datagram. Each datagram consists of a header followed by a data area, which is known as a payload.
    • The size of a datagram is determined by the application that sends data. Allowing the size of datagrams to vary makes IP adaptable to a variety of applications.
    • Has a specific header format
  • Forwarding an IP Datagram
    • As each destination in a forwarding table corresponds to a network, the number of entries in a forwarding table is proportional to the number of networks in the Internet, not the number of hosts.
    • Software examines each table entry by using the mask to extract a prefix of the destination address and comparing the result to the Destination field of the table entry. If they are equal the datagram will be forwarded to the Next Hop in the entry.
    • Longest Prefix Match
      • Resolves ambiguity that can arise when more than one entry matches a destination, by examining entries with the longest prefix first
        • For example: 128.10.0.0/16 would otherwise be equivalent to 128.10.2.0/24
  • Destination Address and Next Hop Address
    • Destination address in a datagram header always refers to the ultimate destination; at each point, a next hop is computed, but the next hop address does not appear in the datagram header.
  • Best-Effort Delivery
    • Since IP is designed to operate over all types of network hardware, including hardware that experiences problems, IP datagrams may not be delivered correctly. Although IP makes a best effort to deliver each datagram, it does not guarantee that it will handle all problems. Such problems include:
      • Data duplication
      • Delayed or out-of-order delivery
      • Corruption of data
      • Datagram loss
  • IP Encapsulation
    • A datagram is encapsulated in a frame for transmission across a physical network. The destination address in the frame is the MAC address of the next hop to which the datagram is being sent. The address is obtained by translating the IP address of the next hop to an equivalent MAC address.
  • Transmission across an Internet
    • When a datagram arrives in a network frame, the receiver extracts the datagram from the frame payload area and discards the frame header.
  • Maximum Transmission Unit (MTU) and Datagram Fragmentation
    • Each network has an MTU that specifies the maximum amount of data a frame can carry. When a router receives a datagram that is larger than the MTU of the network over which it is to be sent, the router divides the datagram into smaller pieces called fragments. Each fragment uses the IP datagram format, but carries only part of the original payload.
  • Reassembly of a Datagram from Fragments
    • The ultimate destination reassembles the fragments, not the next hop router. This has two advantages:
      • Reduces the amount of state information in routers since the router does not need to know whether the datagram is a fragment.
      • Allows routes to change dynamically; if an intermediate router was to reassemble the fragment they would all have to reach that router.
    • Collecting the Fragments of a Datagram
      • Fragments of a datagram can get lost or arrive in an arbitrary order.
      • These segments are reassembled in the correct order by:
        • Referencing a unique identification number in the identification field of each datagram and the IP source address in an incoming fragment to determine the datagram to which the fragment belongs.
        • Additionally, the fragment offset field tells a receiver where the data in the fragment belongs in the original datagram.
      • Consequences of Fragment Loss
        • When the first fragments arrive from a given datagram, the receiver starts a reassembly timer. If all segments arrive before the timer runs out, the receiver cancels the timer and reassembles the datagram.
        • If the timer runs out before all fragments arrive, the receiver discards the fragments that have arrived.
          • There is no mechanism for the receiver to tell the sender what fragments did not arrive.
          • If the sender was to retransmit there is no guarantee the data would travel the same path or be fragmented in the same way.
    • Fragmenting a Fragment
      • If a fragment goes though a router with a smaller MTU than the size of the fragment, it will be fragmented again.
      • IP does not distinguish between original fragments and subfragments.
      • A receiver cannot know whether an incoming fragment is the result of one router fragmenting a datagram or multiple routers fragmenting fragments.
        • Designer work hard to avoid this scenario.
        • The advantage of making all fragments the same is that a receiver can perform reassembly of the original datagram without first reassembing subfragments.
          • Saves CPU time and reduces the amount of header information required in each fragment.

Chapter 23: Support Protocols and Technologies
  •  Address Resolution
    • IP addressses are abstractions provided by protocol software. Since physical network hardware does not know how to locate a computer from its IP address, the next hop address must be translated to an equivalent MAC address before a frame can be sent.
    • Mapping between a protocol address and a hardware address is called address resolution. A host or router uses address resolution when it needs to send a packet to another computer on the same physical network.
      • A computer never attempts to resolve the address of a computer that attaches to a remote network.
    • Address Resolution Protocol (ARP)
      • If computer B needs to resolve the IP address of computer C, computer B broadcasts a request for the MAC address of the computer that has the given IP address. This broadcast travel only across the one network. When it receives the request, computer C sends a directed reply to computer B indicating that it has the IP address in question and giving its MAC address.
      • ARP Message Format
        • Although the ARP message format is sufficiently general to allow arbitrary protocol and hardware addresses, ARP is almost always used to bind an IP address to a 48-bit Ethernet address
      • ARP Caching and Message Processing
        • To reduce network traffic, ARP software extracts and saves the information from responses so it can be used for subsequent packets.
        • The information is kept in a small cache, and when it needs to bind an address, ARP starts by searching the cache.
          • An entry is replaced when a response arrives, and the oldest entry is removed whenever the table runs out of space or after an entry has not been updated for a long period of time (20 minutes)
          • Most computer communication involves two-way traffic, if a message travels from B to C, the probability is high that a reply will travel from C to B.
          • As each address binding requires memory, a computer cannot store an arbitrary number of address bindings.
      • Conceptual Address Boundary
        • ARP forms a conceptual boundary in the protocol stack: layers above ARP use IP, and layers below ARP use MAC addresses.
  • Internet Control Message Protocol (ICMP)
    • Includes both messages about errors and informational messages.
    • ICMP encapsulates messages in IP for transmission, and IP uses ICMP to report problems.
  • Protocol Software, Parameters and Configuration
    • Protocol software is parameterized to allow a compiled binary image to run on multiple computers in a variety of network environments without change. 
    • When a copy of the software is started on a given computer, it must be configured by setting parameters that supply information about the computer and the networks to which it attaches.
  • Dynamic Host Configuration Protocol (DHCP)
    • Allows a computer to move to a new network and obtain configuration information without requiring an administrator to make manual changes to a database.
    • Operation and Optimizations
      • The three most significant performance optimization elements are:
        • Recovery from loss or duplication
        • Caching of server addresses
        • Avoidance of synchronized flooding
  • Network Address Translation (NAT)
    • Allows multiple computers to share a single, globally valid IP address
    • NAT Operation and Private Addresses
      • NAT provides blocks of private (nonroutable) addresses
        • 10.0.0.0/8 - Class A private address block
        • 169.254.0.0/16 - Class B private address block
        • 172.16.0.0/12 - 16 contiguous Class B blocks
        • 192.168.0.0/16 - 256 contiguous Class C blocks
      • The most basic form of NAT replaces the IP source address in datagrams passing from the site to the Internet, and replaces the IP destination address in datagrams passing from the internet to the site.
    • Transport Layer NAT (NAPT)
      • The basic version of NAT described above only handles situations in which each host at a site communicates with a unique server in the Internet. If two hosts at the site attempt to communicate with the same remote server, NAT will not be able to correctly route the incoming datagrams.
      • The solution is to use protocol port numbers to distinguish among services.
        • Entries in the translation table used by NAPT contain a quadruple of source and destination IP addresses and protocol port numbers.
        • NAT is particularly useful in a residence or small business that is sharing an internet connection via Ethernet or Wi-Fi.

Chapter 24: The Future IP (IPv6)
  •  Previous chapters discuss IPv4 which has been extremely successful
    • Made it possible for the Internet to handle heterogeneous networks, dramatic changes in network technologies, and extreme increases in scale.
  • Motivation for change
    • At the current Internet growth rate, each of the possible IPv4 network prefixes will eventually be assigned. Larger addresses are necessary to accommodate continued growth
    • New features could provide special facilities for some applications such as real-time audio and video
    • More complex routing to accommodate replicated services such as Google's distributed data centers or multi-user collaboration tools
  • Since IP is central to all Internet communication, changing IP requires a change to the entire Internet
  • IPv6 Features
    • Address size - 128 bits rather than 32 bits
    • Header format - almost every field in the header has been changed, some have been replaced
    • Extension headers - IPv6 encodes information into separate headers, the base IPv6 header followed by zero or more extension headers, followed by data.
    • Support for Real-time Traffic - includes a mechanism that allows a sender and receiver to establish a high-quality path through the underlying network and to associate datagrams with that path. 
      • Can also be used to associate datagrams with low-cost paths.
    • Extensible protocol - unlike IPv4, IPv6 does not specify all possible protocol features, senders can add additional information to the datagram and new features can be added to the design as needed.
  • IPv6 Datgram Format
    • Base Header
      • Version - identifies the protocol as v6
      • Traffic Class - uses differentiated services to specify general characteristics that the datagram needs
        • Low-latency, low jitter, etc.
      • Flow Label - originally intended to associate a datagram with a particular underlying network path
        • End-to-end flow labels have since fallen out of favor
      • Payload Length - size of the data being carried
      • Next Header - specifies the type of information that follows the current header, if there is an extension header it specifies the type or if no extension header exists it specifies the type of data being carried in the payload.
      • Hop Limit - corresponds to IPv4 "Time-to-Live" field
        • Interpreted stictly, datagram will be discarded if the Hop Limit counts down to zero before the datagram arrives at its destination.
      • Source Address
      • Destination  Address
    • Optional Extension Headers 1 - N
    • Payload
  • Fragmentation, Reassembly and Path MTU
    • IPv6 places fragment information in a separate fragment extension header
      • The presence of this header identifies the datagram as a fragment.
      • The base header and headers that control routing are treated as unfragmentable
    • Fragmentation is performed by the sending host, not by routers as in IPv4. If fragmentation is required, the sending host receives an ICMP error message, and reduces the fragment size until fragments can be sent to the destination.
      • If a router along the path receives a datagram that is larger than the network MTU, it will send an error message and discard the datagram.
      • Path MTU discovery is used to determine the minimum MTU
        • This is an iterative procedure
        • The result is that the sender fragments the datagram into a size equal to the path MTU
  • The Purpose of Multiple Headers
    • Economy
      • Makes it possible to define a large set of features without requiring each datagram header to have at least one field for each feature
    • Extensibility
      • Adding a new feature does not change the existing protocol headers as it would have in IPv4
  • IPv6 Addressing
    • Unicast - the address corresponds to a single computer. A datagram sent to the address is routed along a shortest path to the computer.
    • Multicast - the address corresponds to a set of computers, and membership in the set can change at any time. IPv6 delivers one copy of the datagram to each member of the set.
    • Anycast - the address corresponds to a set of computers that share a common prefix. A datagram sent to the address is delivered to exactly one of the computers (e.g., the computer closest to the sender).
  • IPv6 Colon Hexadecimal Notation
    • Since IPv6 occupies 128 bits the dot decimal notation used to make IPv4 addresses more readable results in 16 numbers separated by dots
    • In order to make this notation more readable Colon Hex is used to represent the address with 16 bits separated by colons.
      • 69DC:8864:FFFF:FFFF:0:1280:8C0A:FFFF
    • Zero compression is also used, replacing a string of zeros with a double colon
      • FF0C:0:0:0:0:0:0:B1 can be written FF0C::B1

Chapter 25: UDP Datagram Transport Service 
  • User Datagram Protocol (UDP)
    • One of two Transmission Control Protocols in the TCP/IP suite (the other is TCP)
    • UDP is less complex and easier to understand than TCP.
      • Know as a "thin protocol layer." 
    • UDP characterized as:
      • End-to-end. 
        • It can distinguish among multiple application programs running on a given computer.
      • Connectionless.
        • The interface it provides to applications follows a connectionless paradigm.
        • Any application can send data at any time and UDP does not transmit any packets other than the packets that carry user data.
      • Message-oriented.
        • An application that uses UDP sends and receives individual messages called user datagrams and consisting of two parts:
          • A short header that specifies the sending and receiving application programs. The header includes:
            • UDP Source Port
            • UDP Destination Port
            • UDP Message Length
            • UDP Checksum - this is optional.
              • When a message arrives at its destination, UDP examines the checksum field and only verifies it if the value is non-zero.
          • A payload that carries the data being sent.
        • If a UDP message is larger than the network MTU, IP will fragment the resulting datagram, which reduces efficiency.
      • Best-effort.
        • Offers the same best-delivery semantics as IP. Arises becuase UDP uses IP for transmission.
        • Communication semantics same as IP so messages can be lost, duplicated, delayed, delivered out-of-order, or corrupted.
        • UDP only suffices for applications such as voice or video that can tolerate delivery errors.
      • Arbitrary interaction.
        • Allows an application to send to many other applications, receive from many other applications, or communicate with exactly one other application.
        •  Modes of Interaction and Broadcast Delivery
          • Four styles of interaction:
            • 1-to-1
            • 1-to-Many
            • Many-to-1
            • Many-to-Many
      • Operating system independent.
        • Provides a means of identifying application programs that does not depend on identifiers used by the local operating system.
        • UDP uses an abstract set of identifiers called protocol port numbers
        • Each computer that implements UDP must provide a mapping between protocol port numbers and the program identifiers that the operating system uses.
    • UDP Checksum and Pseudo Header
      • The UDP header does not include the source of destination IP address
        • This makes UDP smaller and more efficient, but introduces a possibility of error.
      • To confirm that a message has reached the correct destination UDP extends the checksum.
        • When computing the checksum, UDP includes a pseudo header that contains the source, destination and type (i.e., Proto) fields for the IP datagram and a UDP datagram length.
          • The sender computes the checksum as if the UDP header contained extra fields.
          • To verify the checksum, a receiver must obtain the UDP length and the source, destination, and type fields from the IP datagram, then appends them to the UDP message before verifying the checksum.

Chapter 26: TCP Reliable Transport Service
  • Transmission Control Protocol (TCP) is a transport layer protocol that provides reliability.
  • TCP service has seven major features:
    • Connection orientation
      • An application must first request a connection to a destination, and then use the connection to transfer data.
      •  TCP connections are virtual connections because they are achieved in software.
    • Point-to-Point communication
      • Each TCP connection has exactly two endpoints.
    • Complete reliability
      • TCP guarantees that the data sent across a connection will be delivered exactly as sent, complete and in order.
    • Full duplex communication
      • Allows data to flow in either direction, and allows either application program to send data at any time.
    • Stream interface
      • Applications send a continuous stream of octets across a connection. 
      • TCP does not group data into records or messages, and does not guarantee to deliver data in the same size pieces that were transferred by the sending application.
    • Reliable connection startup
      • Allows two applications to reliably start communication.
    • Graceful connection shutdown
      • Before closing a conneciton, TCP ensures that all data has been delivered and that both sides have agreed to shut down the connection.
  • End-to-end protocol 
    • It provides communication between an application on one computer and an application on another computer. 
    • Transport protocols do more than detect errors, they employ techniques that can repair or circumvent problems.
    • Major problems to an end-to-end transport protocol include:
      • Unreliable communication - messages sent across the internet can be lost, duplicated, corrupted, delayed, or delivered out of order.
        • To compensate for corrupted bits a protocol might include parity bits, a checksum, or a cyclic redundancy check (CRC).
        • Sequencing handles duplicates and out-of-order delivery
          • Sending side attaches a sequence number to each packet.
          • Receiving side stores both the sequence number of the last packet received in order, as wellas a list of additional packets that arrived out of order.
          • When a packet arrives the receiver examines the sequence number:
            • If it is the next one expected, it is delivered to the next highest layer and the list is checked to see if other packets can also be delivered.
            • If out of order, the protocol adds the packet to the list.
          • If a packet arrives that has already been delivered or matches one already on the list, the duplicate packet is discarded.
        • To handle packet loss, transport protocols use positive acknowledgement with retransmission.
          • When a frame arrives intact the receiving protocol software sends a small acknowledgement.
          • The sender takes responsibility for ensuring that each packet is transferred successfully.
            • When a packet is sent the sender sets a timer
            •  If no acknowledgement is received before the timer expires, the sender will retransmit the packet.
        • Replay errors in which a delayed packet affects later communication
          • To prevent replay, protocols mark each session with a unique ID and require that ID to be present in each packet.
          • Packets that arrive with an incorrect ID are discarded.
      • End system reboot - at any time during communication either of the two end systems might crash and reboot. There must be no confusion between sessions (some embedded systems can reboot in less time than it takes a packet to cross the internet)
      • Heterogeneous end systems - a powerful sender can generate data so fast that it overruns a slow receiver.
        • Flow control prevents data overrun, several techniques available:
          • Stop-and-go is the simplest form
            • Sender waits after transmitting each packet to receive a control message (usually an acknowledgement) from the receiver.
            • Prevents overrun but results in extremely low throughput.
          • Sliding Window offers high throughput rates
            • Sender and receiver use a fixed window size to determine the amount of data that can be sent before an acknowledgement arrives.
            • The throughput can be increased by increasing the window size, but the network bandwidth imposes an upper bound.
              • Sliding window throughput = min(Network bandwidth, Stopandgo protocol throughput x Window size)
      • Congestion in the Internet - if senders aggressively transmit data intermediate switches and routers can become overrun with packets, analogous to a congested highway.
        •  Transport protocols attempt to avoid congestion collapse by monitoring the network and reacting quickly once congestion starts. There are two basic approaches:
          • Arrange for intermediate systems (routers) to inform a sender when congestion occurs
          • Use increased delay or packet loss as an estimate of congestion
        • Modern network hardware works well, so most delay and loss result from congestion, not hardware failure.
    • Techniques Used in TCP to Handle Packet Loss
      • The delay required for data to reach a destination and an acknowledgement to return depends on traffic in the Internet as well as the distance to the destination. 
      • As TCP allows multiple application programs to communicate with multiple application programs to communicate with multiple destinations concurrently and traffic conditions to affect delay, TCP must handle a variety of delays that can change rapidly.
      • Buffers, Flow Controls and Windows
        • TCP uses a window mechanism to control the flow of data. 
          • A TCP window is measured in bytes.
          • A notification that specifies the size of the window is known as a window advertisement.
            • A receiver sends a window advertisement with each acknowledgement.
            • A sender that receiver a zero window advertisement will stop sending until the receiver again advertises a positive window.
      • TCP's Three-Way Handshake
        • TCP uses the term synchronization segment (SYN segment) to describe the control messages to create a connection, and the term finish segment (FIN segment) to describe the control messages to close a connection. Acknowledgments (ACK). 
        • To start a connection:
          • Each side sends a control message that specifies an initial buffer size (for flow control) and a sequence number. 
            • Host 1: Send syn
            • Host 2: Receiver syn; send syn and ack
            • Host 1: Receive syn and ack; send ack
        • TCP requires each end to generate a random 32-bit sequence  number that becomes the initial sequence for data sent.
            • The probability of replay is very low since TCP chooses a new random number after reboot.
      • TCP Congestion Control
        • Conceptually a transport protocol should reduce the rate of transmission when congestion occurs. 
        • Since it uses an variable size window TCP can achieve a reduction in data rate by temporarily reducing the window size. 
          • In extreme cases where loss occurs, TCP temporarily reduces the window size to half its current value.
      • TCP Segment Format
        • The sequnce number field in a TCP segments gives the sequence number for the first byte of data carried in the segment in the forward direction.
        • An acknowledgement number gives the first sequence number for which data is missing in the reverse direction.

Chapter 27: Internet Routing and Routing Protocols
  • IP routing can be partitioned into two broad categories:
    • Static routing
      • Most Internet hosts use static routing.
        • The host's forwarding table contains two entries: one for the network to which the host attaches, and a default entry that directs all other traffic to a separate router.
    • Dynamic routing
      • Most Internet routers use dynamic routing
        • Each router runs software that learns about destinations other routers can reach, and informs other routers about destinations that it can reach.
        • The routing software uses incoming information to update the local forwarding table continuously.
  • Autonomous Systems
    • The internet is divided into autonomous systems; routers within an autonomous system exchange routing information, which is then summarized before being passed to another group.
    • Two types of Internet routing protocols
      • Interior gateway protocols (IGPs)
        • Usually easy to install and operate, but may limit the size or routing complexity of an autonomous system.
      • Exterior gateway protocols (EGPs)
        • Used to exchange routing information with a router in another autonomous system; and to implement policy constraints.
        • More complex to install and operate than IGPs, but offer more flexibility and lower overhead.
    • Optimal routes, routing metrics and IGPs
      • Although most internet routing protocols are designed to use a hop count metric, it is possible for a network administrator to override the metric to enforce a policy.
      • Within an autonomous system, IGP software uses a routing metric to choose an optimal path to each destination. EGP software finds a path to each destination, but cannot find an optimal path because it cannot compare routing metrics from multiple autonomous systems.
    • Border Gateway Protocol (BGP)
      • Is the exterior gateway protocol that Tier-1 ISPs use to exchange routing information among autonomous systems at the center of the Internet.
        • Current version is BGP-4
      • BGP has the following characteristics:
        • Routing among autonomous systems
        • Provision for policies
        • Facilities for transit routing
        • Reliable transport
    • Routing Information Protocol (RIP)
      • Among the first IGP protocols used in the Internet
      • Has the following characteristics:
        • Routing within an autonomous system
        • Hop count metric
        • Unreliable transport - uses UDP to transfer messages among routers.
        • Broadcast or multicast delivery
        • Support for CIDR and Subnetting
        • Support for default route propagation
        • Distance vector algorithm
        • Passive version for hosts
      • Illustrates a disadvantage of distance vector protocols: the size of a message is proportional to the number of networks that can be reached. 
        • Sending RIP messages introduces delay and processing RIP messages consumes many CPU cycles.
          • Delay means route changes propagate slowly.
        • RIP works well among a few routers, but does not scale well.
    • Open Shortest Path First Protocol (OSPF)
      • Satisfies the demand for a routing protocol that can scale to large organizations. Uses Dijkstra's SPF algorithm to compute shortest paths.
      • OSPF has the following characteristics:
        • Routing within an autonomous system 
        • CIDR support
        • Authenticated message exchange
        • Imported routes - can introduce routes learned from other means such as BGP
        • Link-state algorithm
        • Support for metrics - allows an administrator to assign a cost to each route.
        • Support for multi-access networks - traditional link state routing is inefficient across a multi-access network, OSPF optimizes by designating a single router to broadcast on the network.
      • OSPF Areas
        • Since it allows a manger to partition the routers and networks in an autonomous system into multiple areas, OSPF can scale to handle a larger number of routers than other IGPs.
    • Intermediate System-Intermediate System (IS-IS)
      • An IGP developed at Digital Equipment Corp. created at the same time as OSPF with much of the same functionality. The main differences are:
        • IS-IS was proprietary, OSPF was created as an open standard.
        • OSPF designed to run over IP; IS-IS was designed to run over CLNS (part of the OSI protocol stack that is no longer in use)
        • OSPF was designed to propagate IPv4 routes; IS-IS  was designed to propagate routes for OSI protocols.
        • Over time, OSPF gained many features, as a result IS-IS now has less overhead.
      • Since DEC has dissolved, IS-IS is no longer under copyright protection so a new version was defined in the 2000s to integrate with IP and the internet.
        • The largest ISPs have grown to a size where the extra overhead is OSPF makes IS-IS more attractive. So it is making a comeback.
    • IP Multicast Semantics
      • Membership in an IP multicast group is dynamic: a computer can join or leave a group at any time.
      • Group membership defines a set of receivers; an arbitrary application can send a datagram to the group, even if the application is not a group member.
      • Internet Group Management Protocol (IGMP)
        • Used only on the network between the host and the router.
        • Defines the host, not the application to be a group member.
        • When the last application on a host leaves the group, the host uses IGMP to inform the local router that it is no longer a member of the group.
      • Forwarding and Discovery Techniques
        • Flood and Prune
          • Ideal when group is small and all members are attached to a contiguous LAN.
          • Routers forward each datagram to all networks
          • Uses Reverse Path Broadcasting (RPB) to avoid routing loops by breaking cycles.
          • If a router learns that not hosts on a given network are members of the group, the router prunes the network from the set.
        • Configuration and Tunneling
          •  Ideal when the group is geographically dispersed
          • A router at each site is configured to know about other sites.
          • When a multicast datagram arrives, the router at the site transmits the datagram on all directly attached LANs via hardware multicast.
          • Consults configuration table to determine which remote sites should receive a copy and uses IP-in-IP tunneling to transfer a copy of the multicast datagram to each of the remote sites.
        • Core-based Discovery
          • Allows multicast to scale gracefully from a small group to a large group with members in arbitrary locations.
          • To provide smooth growth, some multicast routing protocols designate a unicast address for each multicast group. 
          • When router1 receives a multicast datagram that must be transmitted to a group, it encapsulates the multicast datagram in a unicast datagram and forwards the unicast datagram to the group's core unicast address. 
          • When the datagram reaches router2 that participates in the group, router2 removes and processes the multicast message.
      • Multicast Protocols
        • Th dynamic characteristics of Internet multicast make the problem of multicast route propagation difficult. 
        • Although many protocols have been proposed, the Internet does not currently have an Internet-wide multicast routing facility.
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)