Interconnecting Links & Networks

• The topic for this week and next week is interconnecting links and networks
• In the past direct links between computers were discussed
• The question is how to interconnect links of the same or similar type to form a large network with a switch (also called bridge)
• Also how to interconnect networks of different types to form an internet with a router (also called gateway)

Switching/Forwarding Principles

• Datagram, Virtual circuit, and Source routing represent these principles

L2 Switches

• Learning bridges and Spanning tree algorithm are used

Internetworking

• IPv4, IP addressing, and forwarding are used

(Packet) Switching/Forwarding Protocols

• Packet is received on one link, then transmitted on one or more other links
• Information in the header of the packet dictates the outgoing link
• Three approaches include datagram, virtual circuit, and source routing

Datagram Networks

• Each packet contains complete destination address
• Each router switch knows next hop for each destination
• Each packet is forwarded independently

Virtual Circuit Networks

• Each packet contains a field identifying its virtual circuit (the VCI, virtual circuit identifier)
• Each router/switch has table of incoming and corresponding outgoing VCs
• Virtual circuit must have been set up in advance

Datagram and Virtual Circuit Switching

• With Datagrams, the host can send data anywhere at any time (connectionless) and complete destination (and source) address is carried in header of every packet
• The switch should be able to determine outgoing link for every address in the network and packets are switched independently, so they may follow different routes
• In large networks, a routing algorithm is needed to fill forwarding table
• In Virtual circuits there is RTT delay before sending data (connection oriented) and only VCI needed in header of data packet
• Switches require entries in forwarding table for established virtual circuits but in the event of failure, a new VC needs to be set up
• Lastly. in a large network, a routing algorithm is needed to decide on outgoing link for set-up message

Datagram and Virtual Circuit Examples

• Datagram examples: Ethernet switches and IP routers
• Virtual circuit examples: X.25, ATM (Asynchronous Transfer Mode), and MPLS (Multi-Protocol Label Switching

Minitel in France

• Minitel installed in French homes in the 1980s and 1990s
• Minitels offered electronic telephone directory, electronic mail, online shopping and banking before the internet
• A "dumb" terminal with a built-in 1200/75 bit/s telephone modem and the backbone connections were over the X.25 network

Ethernet LANs

• Hub: repeater for electrical signals and connected LANs form a single "collision domain"
• Hubs have a limit on total length and number
• Bridge: Each connected LAN has it's own "collision domain" using forwarding table to select outgoing port, automatically filling forwarding table from received frames
• Ethernet switch: bridge with many ports, separate port for each host

Learning Bridge Operations

• Learn source address of incoming frames
• Use to choose on which port to send outgoing frames
• When frame received at bridge: Record incoming port and address of sending host in forwarding table then lookup destination address in forwarding table
• If destination is on the port from which the frame arrived, drop and forward accordingly
• If the destination has no entry, forward out all ports except the incoming port

Spanning Tree Algorithm

• Automatically switch off some ports, so no loops in the network remain
• Reduce the network topology to a spanning tree.
• Strategy: Every bridge has unique identifier, and the bridge with lowest identifier becomes root until they learn otherwise
• Root bridge sends out configuration messages, which are relayed by other bridges and the bridges then find shortest path to root and construct spanning tree

Bridge Limitations

• Do not support heterogeneity between different LANs
• Do not scale well
• Non-optimal routes
• Leads to large forwarding tables
• Root bridge may become bottleneck and flooding of initial packet wastes resources

Internetworking

• A collection of networks interconnected to provide some sort of host-to-host packet delivery service

IP Service Model

• Provides a global addressing scheme in which all hosts on the internet can identify each other
• Datagram delivery is best-effort, thus, packets may be lost, delayed, delivered out-of-order duplicated, or use any underlying network

Fragmentation and Reassembly

• Fragmentation involves dividing large IP datagrams within a network in order to accommodate links with limited MTUs
• Datagrams may be fragmented into several smaller datagrams
• Reassembly occurs only at final destination
• IP header identifies and orders related fragments

Global IP Addresses

• Routers and hosts have a globally unique address for each interface
• IP address uses 32 bits (4 billion addresses)
• The 32 bits are arranged as 4 groups of 8 bits (written in decimal)
• IP addresses have a hierarchical structure that's split into network and host parts

Pre-1994 Class Addresses

• Class A address: 0nnnnnn hhhhhhhh hhhhhhhh hhhhhhhh, supports 127 networks of 16 million hosts
• Class B address: 10nnnnnn nnnnnnnn hhhhhhhh hhhhhhhh, supports 16384 networks of 65534 hosts
• Class C address: 110nnnnnn nnnnnnnn nnnnnnnn hhhhhhhh, supports 2 million networks of 254 hosts

IP Datagram Forwarding Strategy

• Every IP datagram contains the destination IP address
• Each router maintains a forwarding table; forward to destination if directly connected
• Otherwise, send datagram to the next-hop router

Subnetting

• Involves adding a level to address/routing hierarchy for subnets by defining a variable partition of host part of addresses
• Subnets are visible only within site

Class InterDomain Routing (CIDR)

• Abolishes IP address classes A/B/C for inter-domain routing
• An institution with a certain amount of nodes is allocated its own range which gets added to global forwarding tables to avoid the need to allocate each subnet individually
• Without CIDR, institutions needing a certain allocation of addresses were bound to either waste addresses by requesting Class A/B, or having to request several Class C allocations that all had to be added to global forwarding tables

Longest Prefix Match

• In the absence of CIDR, forwarding backbones were very straight forward in that the network was simply determined by IP class (A, B or C) and forwarded accordingly
• With CIDR, an address from several forwarding entries: the most specific is chosen

Internet Control Message Protocol (ICMP)

• This is a simple protocol used for error reporting
• Most important messages: destination unreachable due to network, host, protocol, or port reason and fragmentation failures
• Time exceeded indicates that TTL reached zero and not all fragments arrived
• Lastly, it issues echo requests and replies (ping) which is useful for testing