Principles of Routing

Virtual Circuits and Datagrams

• The transport layer uses the network layer's host-to-host communication service to provide process-to-process communication.
• The network layer implements host-to-host communication.
• A piece of the network layer exists in every host and router.
• Network-layer protocols are challenging due to this.

Network Layer

• The network layer is a complex layer in the protocol stack.
• The network layer uses two broad approaches for packet delivery:
  • Datagram model
  • Virtual-circuit model

Forwarding vs. Routing

• Forwarding: transferring a packet from an incoming link to an outgoing link within a single router.
• Routing: determining the paths packets take from source to destination node, involving all routers in a network interacting via routing protocols.

Packet Forwarding

• Packet forwarding involves:
  • Router hardware architecture and organization
  • Internet Protocol (IP)
  • Network-layer addressing
  • IPv4 datagram format
  • Network address translation (NAT)
  • Datagram fragmentation
  • Internet Control Message Protocol (ICMP)
  • IPv6

Routing Function

• The job of a routing algorithm is to determine good paths from senders to receivers.
• Routing algorithm types:
  • Link-state
  • Distance vector
• Hierarchical routing is considered due to the complexity of routing algorithms as network routers increase.
• Internet routing protocols:
  • Intra-autonomous system: RIP, OSPF, IS-IS
  • Inter-autonomous system: BGP

Network Communication

• Host H1 sends information to Host H2.
• The network layer at H1 encapsulates segments from the transport layer into datagrams and sends them to router R1.
• At H2, the network layer receives datagrams from router R2, extracts transport-layer segments, and delivers them to the transport layer at H2.

Router Role

• The primary role of routers is to forward datagrams from input links to output links.
• Routers typically don't run application- and transport-layer protocols, except for control purposes.

Network Layer Services

• A transport layer can offer connectionless or connection-oriented service between processes.
• The Internet's transport layer offers applications a choice:
  • UDP (connectionless)
  • TCP (connection-oriented)
• A network layer can provide connectionless or connection service between hosts.

Network Layer Services Parallels

• Network-layer connection and connectionless services parallel transport-layer services.
• Network-layer connection service begins with handshaking between source and destination hosts.
• Network-layer connectionless service has no handshaking.

Differences in Services

• Network layer services are host-to-host services provided by the network layer for the transport layer.
• Transport layer services are process-to-process services provided by the transport layer for the application layer.
• Computer network architectures provide either host-to-host connectionless or connection services, but not both.

Network Types

• Virtual-circuit (VC) networks: provide only a connection service at the network layer.
• Datagram networks: provide only a connectionless service at the network layer.

Implementation Differences

• Transport-layer connection-oriented service is implemented at the edge of the network in the end systems.
• Network-layer connection service is implemented in routers in the network core and end systems.

Virtual-Circuit Networks

• Virtual-circuit networks use connections at the network layer.
• Network-layer connections are called virtual circuits (VCs).

VC Components

• A VC consists of:
  • A path (series of links and routers) between source and destination hosts
  • VC numbers, one for each link along the path
  • Entries in forwarding tables in each router along the path
• A packet belonging to a VC carries a VC number in its header.
• Each router replaces the VC number with a new one from its forwarding table.

VC Number Replacement

• Based on link interface numbers, a host A requests a VC be established to host B, with path A-R1-R2-B.
• VC numbers 12, 22, and 32 are assigned to the three links for this VC.
• When a packet leaves A, the VC number field is 12; when it leaves R1, it is 22; and when it leaves R2, it is 32.

Router Determination

• Routers determine the replacement VC number using forwarding tables.
• Each router's forwarding table includes VC number translation.
• Example forwarding table in R1:

VC Management

• When a new VC is established across a router, an entry is added to the forwarding table.
• When a VC terminates, the entries in each table along its path are removed.

VC Number Uniqueness

• Packets don't keep the same VC number on each link for two reasons:
  • Reduces the length of the VC field in the packet header.
  • Simplifies VC setup by permitting a different VC number at each link.
• Each link can choose a VC number independently of others.
• If a common VC number were required, routers would have to exchange many messages to agree on one not already in use.

Connection State Information

• Routers in a VC network must maintain connection state information for ongoing connections.
• When a new connection is established, an entry is added to the router’s forwarding table.
• When a connection is released, an entry is removed.
• Even without VC-number translation, connection state must be maintained to associate VC numbers with output interface numbers.
• Whether a router maintains connection state is a crucial factor.

VC Phases

• Three phases in a virtual circuit:
  • VC setup: The sending transport layer contacts the network layer, specifies the receiver’s address, and waits for the network to set up the VC.
    • The network layer determines the path between sender and receiver.
    • The network layer also determines the VC number for each link along the path.
    • Finally, the network layer adds an entry in the forwarding table in each router along the path.
    • May also reserve resources (e.g., bandwidth) along the path.
  • Data transfer: Packets flow along the VC once it's been established.
  • VC teardown: Initiated when the sender (or receiver) informs the network layer of its desire to terminate the VC.
    • The network layer informs the end system on the other side and updates forwarding tables in each router to indicate the VC no longer exists.

VC Setup

• VC setup at the network layer differs subtly from connection setup at the transport layer (e.g., TCP three-way handshake).
• Transport-layer connection setup involves only the two end systems.
• Routers within the network are oblivious to it.
• With a VC network layer, routers along the path are involved in VC setup, and each router is fully aware of all VCs passing through it.

Signaling Messages

• Messages that end systems send to initiate or terminate a VC, and messages passed between routers to set up the VC, are known as signaling messages.
• The protocols used to exchange these messages are often referred to as signaling protocols.

Datagram Networks

• In a datagram network, each time an end system wants to send a packet, it stamps the packet with the destination end system's address and sends it into the network.
• There is no VC setup.
• Routers do not maintain VC state information.

Router Functionality

• As a packet is transmitted through routers:
  • Each router uses the packet’s destination address to forward it.
  • Each router has a forwarding table that maps destination addresses to link interfaces.
  • The router uses the destination addresses to look up the output link interface.
  • The router forwards the packet to that output link interface.

Forwarding Table Implementation

• If destination addresses are 32 bits, a brute-force implementation would have an entry for every possible address.
• Since there are over 4 billion possible addresses, this is not feasible.

Forwarding Example

• Router has four links, numbered 0 through 3. Packets are forwarded to the link interfaces as follows:

Forwarding Table Optimization

• Avoid 4 billion entries.
• Use following forwarding table with just four entries:

Forwarding Process

• Router matches a prefix of the packet’s destination address with the entries in the table.
• If there is a match, the router forwards the packet to a link associated with the match.
• Example: If destination address is 11001000\ 00010111\ 00010110 \10100001, the router forwards the packet to link interface 0.
• If a prefix doesn’t match any of the first three entries, then the router forwards the packet to interface 3.

Longest Prefix Matching Rule

• If a destination address matches more than one entry, the router uses the longest prefix matching rule.
• It finds the longest matching entry in the table and forwards the packet to the link interface associated with the longest prefix match.
• Example: Address 11001000\ 00010111\ 00011000 \10101010 matches the second and third entries, router uses the second because 24 bits > 21 bits.

Forwarding Table Maintenance

• Routers in datagram networks don’t maintain connection state information, but they maintain forwarding state information in forwarding tables.
• The forwarding state information changes relatively slowly.
• Forwarding tables are modified by the routing algorithms, which typically update a forwarding table every one to five minutes.
• In a VC network, a forwarding table is modified whenever a new connection is set up or torn down, possibly at a microsecond timescale.

Variable Paths

• Because forwarding tables in datagram networks can be modified at any time, a series of packets sent from one end system to another may follow different paths and may arrive out of order.

Principles of Routing

• Input Processing
  • Figure 4.7 shows a more detailed view of input processing.
  • Lookup in the input port central
    • the router uses the forwarding table to look up the output port to which an arriving packet will be forwarded via the switching fabric.
  • The forwarding table is
    • Computed and updated by the routing processor, with a shadow copy typically stored at each input port.
  • With a shadow copy,
    • Forwarding decision can be made locally, at each input port, without invoking the centralized routing processor on a per-packet basis thus avoiding a centralized processing bottleneck.

IP Address Lookup

• Given the existence of a forwarding table,
  • Lookup is conceptually simple
    • search through the forwarding table looking for the longest prefix match
  • But at Gigabit transmission rates,
    • This lookup must be performed in nanoseconds.
  • Thus, not only must lookup be performed in hardware,
    • But techniques beyond a simple linear search through a large table are needed; surveys of fast lookup algorithms can be found.
  • Special attention must be paid to memory access times, resulting in designs with embedded on-chip DRAM and faster SRAM (used as a DRAM cache) memories.
  • Ternary Content Address Memories (TCAMs) are also often used for lookup.

CAM Configuration

• With a TCAM, a 32-bit IP address is presented to the memory, which returns the content of the forwarding table entry for that address in essentially constant time.
• The Cisco 8500 has a 64K CAM for each input port.

Output Port Determination

• Once a packet’s output port has been determined via the lookup, the packet can be sent into the switching fabric.
• In some designs, a packet may be temporarily blocked from entering the switching fabric if packets from other input ports are currently using the fabric.
• A blocked packet will be queued at the input port and then scheduled to cross the fabric at a later point in time.

Additional Actions

• Input Ports Also
  • Physical- and link-layer processing must occur
  • The packet’s version number, checksum and time-to-live field must be checked and the latter two fields rewritten; and
  • Counters used for network management (such as the number of IP datagrams received) must be updated.
  • The input port steps of looking up an IP address (“match”) then
  • Sending the packet into the switching fabric (“action”)
• Is a specific case of a more general “match plus action” abstraction that is performed in many networked devices, not just routers.

Packets and Firewalls

• In firewalls, devices that filter out selected incoming packets: an incoming packet whose header matches a given criteria.
• combination of source/destination IP addresses and transport-layer port numbers: may be prevented from being forwarded (action).

Input Packets

• In a network address translator (NAT), an incoming packet whose transport-layer port number matches a given value will have its port number rewritten before forwarding (action).
• Thus, the “match plus action” abstraction is both powerful and prevalent in network devices.

Switching Fabric (Router Heart)

• The switching fabric is at the very heart of a router, as it is through this fabric that the packets are actually switched (that is, forwarded) from an input port to an output port.
• Switching can be accomplished in a number of ways, switching via memory, Switching via bus switching via interconnection network.

Switching via Memory

• The simplest, earliest routers were traditional computers, with switching between input and output ports being done under direct control of the CPU (routing processor).
• Input and output ports functioned as traditional I/O devices in a traditional operating system.
• An input port with an arriving packet first signaled the routing processor via an interrupt.

Switching and Memory

• The packet was copied from the input port into processor memory.
• The routing processor then extracted the destination address from the header, looked up the appropriate output port in the forwarding table, and copied the packet to the output port’s buffers.
• In this scenario, if the memory bandwidth is such that B packets per second can be written into, or read from, memory, then the overall forwarding throughput (the total rate at which packets are transferred from input ports to output ports) must be less than B/2.

Multiple Packets

• Two packets cannot be forwarded at the same time, even if they have different destination ports, since only one memory read/write over the shared system bus can be done at a time.

Modern Switching via Memory

• Many modern routers switch via memory.
• Major difference from early routers, is that the lookup of the destination address and the storing of the packet into the appropriate memory location are performed by processing on the input line cards.
• In some ways, routers that switch via memory look very much like shared-memory multiprocessors, with the processing on a line card switching (writing) packets into the memory of the appropriate output port.

Switching Via a Bus

• In this approach, an input port transfers a packet directly to the output port over a shared bus, without intervention by the routing processor.
• The local output port to which this packet is being transferred and transmitting the packet onto the bus.
• The packet is received by all output ports but only the port that matches the label will keep the packet.

Packet Arrival

• If multiple packets arrive to the router at the same time, each at a different input port, all but one must wait since only one packet can cross the bus at a time.
• Because every packet must cross the single bus,
  • the switching speed of the router is limited to the bus speed;
  • switching via a bus is often sufficient for routers that operate in small local area and enterprise networks.

Interconnection switching

• One way to overcome the bandwidth limitation of a single, shared bus is to use a more sophisticated interconnection network, such as those that have been used in the past to interconnect processors in a multiprocessor computer architecture.
• A crossbar switch is an interconnection network consisting of 2N buses that connect N input ports to N output ports

Output processing

• Output port processing takes packets that have been stored in the output port’s memory and transmits them over the output link.
• This includes selecting and de-queueing packets for transmission, and
• performing the needed link layer and physical-layer transmission functions.

Internet Protocol (IP)

• Internet addressing and forwarding are important components of the Internet Protocol (IP).
  • IPV4 &IPV6 versions

3 network Layer components

• The Internet’s network layer has three major components.
  • The first component is the IP protocol.
  • The second major component is the routing component, which determines the path datagram follows. Routing protocols compute the forwarding table.
  • The final component of the network layer is a facility to report errors in datagrams respond to requests for certain network-layer information.
    • Internet’s network-layer error- and information-reporting protocol, the Internet Control Message Protocol (ICMP).
      Datagram format plays a center role in the Internet

Format of IPv4

• The major fields datagram version number, Header length, type of Services. Datagram length, Identifer , flags , fragmentation offset, Time to live , upper-layer protocol , header checksum, source/ destination IP address, Options , data.

IPv4 Fields:

• Version number:

  • Specifies IP protocol version.
  • Router can determine how to interpret the datagram.
  • IP versions use different datagram formats.
  • Current version is IPv4, a new version of IP is (IPv6).

• Header length:

  • IPv4 datagrams can contain a variable number of options.
  • Determines where in the IP datagram the data begins.
  • Typical IP datagram has a 20-byte header.

• Type of service:

  • Allows differentiation of IP datagrams (e.g., low delay, high throughput, or reliability).
  • Distinguishes real-time (IP telephony) and non-real-time (FTP) datagrams.

• Datagram length:

  • Total length of the IP datagram (header plus data), measured in bytes.
  • Theoretical maximum size is 65,535 bytes,16 bits long

• Identifier, flags, fragmentation offset:

  • Associated with IP fragmentation.
  • IPv6 does not allow for fragmentation at routers.

• Time-to-live:

  • Ensures that datagrams do not circulate forever in the network.
  • Decremented each time the datagram is processed by a router.
  • If TTL reaches 0, the datagram must be dropped.

• Protocol:

  • Indicates the specific transport-layer protocol. Used only destination is reached.
  • Example: 6 indicates TCP, 17 indicates UDP.

• Header checksum:

  • Aids a router in detecting bit errors in a received IP datagram.
  • Treat each 2 bytes in the header as a number and summing these numbers using 1s complement arithmetic. The 1s complement of this sum, known as the Internet checksum, is stored in the checksum field.

• Source and destination IP addresses:

  • Source inserts its IP address into the source IP address field destination inserts the address of it into the destination IP address field

• Options:

  • Allows an IP header to be extended.

• Data (payload):

  • Data field contains the transport-layer segment (TCP or UDP) to be delivered to the destination.
  • Data field can carry other data types, such as ICMP messages.
  • IP datagram has 20 bytes of header (no options).
  • If the datagram carries a TCP segment, the header is 40 bytes.

Datagram Fragmentation

• Maximum transmission unit (MTU) is the maximum amount of data unit or Protocols can carry.
• IP datagrams are encapsulated within link-layer frames.
• Each IP datagram is encapsulated within the link-layer frame for transport from one router to the next router
  *Interconnection better forwarding table

IP data gram Fragment

• Fragmentation is checked for outgoing links with MTU smaller than IP datagram length

Data Fragment Implementation
*Fragments are reassembled before reaching transport layer at destination.
*TCP, UDP are expecting segment from network layer
*Ipv4 datagrams reassembly job is located in the end system rather than in the network routers.

Data Fragments Task

*Datagrams are created sending identification number source and destination address increment datagram each sends.
*Each datagram (fragment) is stamped with source/destination address, identification number when a router needs fragment a datagram .When Destination receives series of datagram form the host ,Identification examined determine whether datagram has larger datagram
*Flag bit in 0, ensures whether host has received last fragment number order proper assembly order is determined and the offset is indicated.

Datagram Fragments Protocol issues to Accommodate:

*Complicated routers and end systems
*Cause of DoS Attacks (Jolt 2 )

IPv4 Addressing

*Hosts connect into network singl link over IP address to send datagram
*Boundary called the interface.
*Ip addresses are 32 bit and 4 bytes called dotted decimal for notation,separated by a period from other bytes in the address (193.32.216.9).

IPv4 Addressing notes

*Each interface needs an IP address, Each address needs to be globally unique. Address is determined by subnet to which is connected.
*Subnets/ Ip network has no router and the IP addressing sends address through subnet. The use of mask defines the number of bit of number

Sub Addressing in IPv4

*Point to point links are used.
*Organization with multiple Ethernet can generate segments with each segment having the same subnet.

Obtaining Blocks addresses

*To obtain Block ip address admin needs to contact ISP to provide address use within subnet, ISP would obtain from IP address space managed by internet of ICANN based on guidelines.
*Roles of Non profit ICANN manage to allocate ip addresses and manage domain names, DNS root server and domain disoutes.

Obtaining Host address By DHCP

*Allows a host to obtain receive the Ip address from the server configured in the system in automated fashion.
*DHCP also enables learning subnet network DNS,subnet gateway.

Dynamically configured Plug and Play Protocol (DHCP)

*Dhcp clients allows aspect connecting host to network.
*Enjoys widespread use resident internet and wireless LANs as host joins and leaves.
*DHCP automated configures mobility access in library to laptops when the system needs a new number
Updates as Server needs IP address to current host.

DHCP Client/Server side configuration

*Client configuration the new array host that wants to obtain configure info inclunding IP address.
*server server a subnet contains a DHCP address for new connected hosts.

• DHCP four step Process:

1. DHCP server discovery

2. DHCP server offer(s).

3. DHCP request.

4. DHCP ACK.

DHCP server discovery:

*newly arriving host with with sends a DHCP DISCOVER message using UDP packed that needs to broadcasted to network to look up a DHCP server . The packed is encapsulates within an IP datagram

DHCP offers

*DHCP broadcast the server on the subnet on it as to broadcast client from it
*Contains the transaction ID, proposed IP address and validity lifetime.

DHCP request messages

*Client choose one or more from the message send back

DHCP ACK messages

• Server gives a ack for configuration parameters to the address allocated after inter action duration.

Network Address Translation (NAT)

*Used for Home Networks with Routers
*Limited on public Internet Addresses, home or local addresses can use address space reserved
*NAT enabled router has interface home network the addressing exact same network home subnet
*The address space is one of the three portion that is only accessible to devices inside the nework.
*Devices with in home network and connect to same network with these addresses.
*Packets forwarded can use these addresses to send beyond homes and network.

NAT translation operation

*Translates the router like the outside world, NAT router behaves a single IP address

• Traffic have single IP addresses.
• NAT hides the details of home network for the outside world. This makes the router understand the host to forward packet

NAT Tables

• Uses port number of IP address based on value to the table
• the host 10.0.1 with sends to Web Server 5001 , HTTP requets , When the NAT Router uses router indexes NAT with detination IP that has network proper to network.

IPv6

*To tackle the exhaustion of IPv4 IP addresses. An IP address that has its address increase from 34 to 128 bits

IPv6 Details of Expanded adressing

Ensuring that world does not use ip numbers has unicast and multicast with anycast addresses
New and expanded 40 byes header to make processing easier
Flexible approach traffic flow easier and quality is improved
Allows labelling of packets for better service etc.

IPv6 details on datagram format

*Version of address
*Traffic class
*Flow label
*Payload length
*Next header
*Hop limit
*Source and destination address
*Data

IPv6 Additional attributes to make it different from older IPv4 implementations

*Fragmentation /reassmebly - Ipv6 does not allow this to go middle only at end

• Header checksum - Not supported in this version, data verification is done at higher layers
  *Options - Possible next headers are pointed to by header, thus headers are of fixed length

Transitioning from IPv4 to IPv6

*Dual stack approach
*Tunneling: Ipv6 uses this approach so the Ipv4 can forward them over the inter connected channels.

Transition Table

• It computes the least cost path from one node ( the source which is referred to as A ) to all nodes in the network.
• It is iterative and has the property that after the K iteration of the algorithm , the lease cost path known to all K known nodes and the least cost path will have path of least cost.
  Cost from mode i to node j. Not direct the cost C(i,y) =infty.
  Notation
  C(I ,J): link Cost from node i to node j. if Nodes i and j are not defined directly them, C(I, J)=infinifty.
  D(y): The node is the Cost of Path from the Source Node to the final Destinantion V that has currently the lowest.
  P(y): Is the Node is previous to V along current listcost from source to v.