Chapter 5: Computer Networks

Network Layer

Network Layer

The layer of the OSI model that is responsible for getting packets from the source to the destination, including routing and path computation.

Data Link Layer

The layer of the OSI model that focuses on moving frames from one end of a virtual wire to the other, in contrast to the network layer which deals with end-to-end transmission.

Topology

The set of all routers and links in a network.

Autonomous Systems

Independently operated networks that may require coordination of traffic flows and network utilization at the network layer.

Software-Defined Networking

A network architecture that allows the network layer to be configured from higher-level software programs, enabling greater flexibility and control.

Network Layer Protocol

The protocol used at the network layer, such as IP (Internet Protocol) in the case of the Internet.

Store-and-Forward Packet Switching

The mechanism used in the network layer where packets are stored at each router until they have fully arrived and are then forwarded to the next router along the path.

Transport Layer

The layer of the OSI model that receives services from the network layer and is shielded from the details of the routers and network topology.

Datagram Network

A type of network where packets are injected into the network individually and routed independently of each other, without the need for advance setup.

Virtual Circuit Network

A type of network where a path from the source router to the destination router is established before any data packets can be sent, similar to the setup of physical circuits in the telephone system.

Connection identifier

A unique identifier used to establish a virtual circuit between two hosts in a network.

Conflict

A situation where there is a clash or overlap in the use of connection identifiers, causing difficulty in distinguishing packets from different connections.

MPLS (MultiProtocol Label Switching)

A connection-oriented network service used within ISP networks, where IP packets are wrapped in an MPLS header with a connection identifier or label.

Virtual-Circuit Network

A network that establishes a virtual circuit between hosts before transmitting data packets, requiring circuit setup and using connection identifiers for routing.

Datagram Network

A network that does not require circuit setup and routes each data packet independently, using source and destination addresses for routing.

Routing

The process of determining the path or route for transmitting packets from the source to the destination in a network.

Forwarding

The process of selecting the outgoing line or interface for a packet based on the routing decision made by the router.

Correctness

A desirable property of a routing algorithm that ensures the selected routes are accurate and lead to successful packet delivery.

Robustness

A desirable property of a routing algorithm that enables it to handle changes in network topology and traffic without causing disruptions or failures.

Stability

A desirable property of a routing algorithm that allows it to reach equilibrium and maintain a fixed set of paths, even in the presence of changes in the network.

Fairness

A desirable property of a routing algorithm that ensures equitable distribution of network resources among different connections or flows.

Efficiency

A desirable property of a routing algorithm that maximizes the utilization of network resources and minimizes delays or congestion.

Nonadaptive Routing Algorithm

A routing algorithm that does not consider real-time measurements or estimates of network conditions, but instead precomputes and downloads routes to routers.

Adaptive Routing Algorithm

A routing algorithm that dynamically adjusts routing decisions based on real-time information about network topology and traffic.

Optimality Principle

A principle stating that if a router is on the optimal path from one router to another, then the optimal path from that router to the destination also follows the same route.

Sink tree

A tree structure used in routing algorithms that does not contain any loops and ensures that each packet is delivered within a finite and bounded number of hops.

Shortest path algorithm

A technique for computing optimal paths in a network by building a graph representation of the network and finding the shortest path between two nodes on the graph.

Shortest path

The path between two nodes in a network that has the minimum length according to a given metric, such as the number of hops or geographic distance.

Flooding

A routing technique where every incoming packet is sent out on every outgoing line except the one it arrived on, ensuring that the packet is delivered to every node in the network.

Hop count

A counter contained in the header of each packet that is decremented at each hop, used to limit the number of hops a packet can take and prevent infinite flooding.

Sequence number

A unique identifier assigned to each packet by the source router, used to track which packets have been flooded and avoid sending them out again.

Dijkstra's algorithm

A shortest path algorithm that finds the shortest paths between a source and all destinations in a network by iteratively updating the labels of nodes based on the current shortest path.

Flooding as a building block

Flooding can be used as a basic routing algorithm that requires little setup and is robust, making it suitable for use in more complex and efficient routing algorithms.

Robustness

The ability of a routing algorithm to continue functioning and find a path even in the presence of failures or disruptions in the network.

Metric

A measure used to evaluate the length or quality of a path in a network, such as the number of hops, physical distance, or delay.

Dynamic routing algorithms

Algorithms used in computer networks that find shortest paths for the current topology.

Distance vector routing

A dynamic routing algorithm where each router maintains a table giving the best known distance to each destination and which link to use to get there.

Link state routing

Another dynamic routing algorithm that is popular in computer networks.

Distributed Bellman-Ford routing algorithm

Another name for the distance vector routing algorithm, named after the researchers who developed it.

Routing table

A table maintained by each router that contains entries for each router in the network, including the preferred outgoing line to use for that destination and an estimate of the distance to that destination.

Metric

A measurement used to determine the distance to a destination in the routing table, such as the number of hops or propagation delay.

Convergence

The settling of routes to best paths across the network.

Count-to-infinity problem

A problem in distance vector routing where bad news travels slowly, causing the algorithm to converge slowly after network topology changes.

Link state routing

A routing algorithm that replaced distance vector routing in the ARPANET in 1979 due to its faster convergence time.

Dijkstra's algorithm

An algorithm used in link state routing to compute the shortest path to every other router.

Link State Routing Algorithm

A routing algorithm that requires each link to have a distance or cost metric for finding shortest paths.

Cost Metric

The distance or cost assigned to each link in the network, which can be set automatically or configured by the network operator.

Bandwidth

The capacity of a link, often used as a basis for determining the cost of the link in link state routing algorithms.

Delay

The time it takes for a packet to travel from one end of a link to the other, which can be factored into the cost of the link in link state routing algorithms.

ECHO Packet

A special packet sent over a link to measure the round trip time and estimate the delay of the link.

Link State Packet

A packet containing information about the network topology, including the identity of the sender, sequence number, age, list of neighbors, and cost to each neighbor.

Flooding

A method used to distribute link state packets to all routers in the network by forwarding the packet on all lines except the one it arrived on.

Sequence Number

A number included in each link state packet to keep track of the order in which packets are sent and received.

Routing Table

A data structure used by routers to store information about the network topology and determine the shortest paths to different destinations.

Hierarchical Routing

A routing approach that divides routers into regions or areas, where each router knows the details of routing within its own region but knows nothing about the internal structure of other regions.

Hierarchical routing

A routing method that condenses multiple regions into a single router, reducing the size of the routing table.

Routing table

A data structure that contains information about the available routes in a network, including destination addresses and corresponding output lines.

Path length

The number of hops or steps required to reach a destination in a network.

Broadcast routing

A method of sending messages to many or all other hosts in a network simultaneously.

Multidestination routing

A routing technique where each packet contains a list of destinations or a bit map indicating the desired destinations.

Flooding

A broadcast routing technique that sends a packet to all destinations by forwarding it to all connected links.

Reverse path forwarding

A broadcast routing algorithm that forwards copies of a broadcast packet onto all links except the one it arrived on, based on the assumption that the first copy to arrive at a router is the one that followed the best route.

Spanning tree

A subset of a network that includes all routers but contains no loops, used in multicast routing to efficiently deliver packets to members of a group.

Multicast routing

A routing algorithm used to send messages to well-defined groups that are numerically large in size but small compared to the network as a whole.

Pruning

The process of removing links from a spanning tree that do not lead to members of a multicast group, resulting in an efficient multicast spanning tree.

Pruned Spanning Tree

A spanning tree constructed by removing all links that do not connect group members to the sink node.

MOSPF (Multicast OSPF)

An example of a link state protocol that constructs pruned spanning trees for multicast groups.

Reverse Path Forwarding

A pruning strategy in distance vector routing where routers respond with PRUNE messages to stop receiving multicast messages for a particular group.

DVMRP (Distance Vector Multicast Routing Protocol)

An example of a multicast routing protocol that uses reverse path forwarding for pruning.

Core-Based Trees

A design alternative that computes a single spanning tree for a multicast group by agreeing on a root (core) and building the tree based on packets sent from each member to the core.

Anycast Routing

A delivery model where a packet is delivered to the nearest member of a group.

Anycast

A scheme where nodes are given the same address and the routing protocol chooses the shortest path to the nearest instance of the destination.

Congestion

A situation where too many packets in a network can lead to packet delay and loss, degrading performance.

Congestion Collapse

A situation where increasing load on the network results in less traffic being successfully delivered, often due to excessive delays or retransmissions.

Traffic Management

Practices and mechanisms used by the network layer to control and manage congestion in the network.

Flow Control

A mechanism that ensures the sender does not transmit data faster than the receiver can process it, preventing data loss due to overwhelming the receiver's capacity.

Congestion

When the total offered traffic exceeds what the network can handle.

Congestion control

Slowing down the sending rates of traffic flows to prevent congestion.

Flow control

Slowing down the sending rates of traffic flows either because the receiver or the network cannot handle the load.

Traffic management

Approaches applied by network operators to handle congestion and control traffic.

Traffic-aware routing

Routing approach that takes into account changes in traffic load to shift traffic away from congested paths.

Admission control

Technique used in virtual-circuit networks to prevent congestion by refusing new connections if the network capacity cannot support them.

Throttling

Slowing down the traffic flow by requesting sources to decrease their sending rates.

Load shedding

Discarding packets that the network cannot deliver to prevent congestion collapse.

Provisioning

Building a network that is provisioned for the traffic load it must carry to avoid congestion.

Traffic shaping

Restricting the transmission rate for a particular sender to prevent congestion.

Traffic policing

Dropping traffic from a particular sender if it exceeds a certain rate to prevent congestion.

Leaky bucket

A mechanism for performing traffic shaping that bounds the average rate and instantaneous burst size of traffic.

Multipath routing

Routing approach that allows multiple paths from a source to a destination to spread traffic and avoid congestion.

Traffic engineering

Adjustments made to routing protocols on slower time scales to optimize network traffic flow.

Load shedding policy

The decision-making process of routers to determine which packets to drop when the network is congested.

Load shedding

A technique used to manage network congestion by discarding packets based on their importance or priority.

Routing packets

Packets that carry routing information and are more important than regular data packets because they establish routes in the network.

Compressing video

Algorithms like MPEG that transmit an entire frame and then send subsequent frames as differences from the last full frame to save bandwidth.

Discard policy

A policy where applications mark their packets to indicate their importance, allowing routers to drop packets from the least important class first during congestion.

Traffic shaping

A technique for regulating the average rate and burstiness of data flow entering the network to match the network's capacity.

Service Level Agreement (SLA)

An agreement between the customer and the network provider that defines the traffic pattern and quality of service guarantees.

Traffic policing

The process of monitoring a traffic flow to ensure that it adheres to the agreed-upon traffic pattern.

Leaky bucket algorithm

A traffic shaping algorithm where packets are queued until enough "water" leaks out of the bucket to hold them or they are discarded if the bucket is full.

Token bucket algorithm

A traffic shaping algorithm where packets can be sent as long as there are "tokens" available in the bucket, with a maximum number of tokens that can accumulate.