Notes on Routing and Error Correction

WANs are made of store and forward switches.

Each switch has a routing table giving the next hop to a destination. The table may contain a default next hop for sites not listed in the table. Routing tables can also contain a second choice route in the event the first route is unavailable or congested. Global routing is done by local decisions.

Hierarchical addresses can be used to simplify routing.

There are several algorithms for computing the optimal path.

Connection oriented and connectionless systems.

Issue Connection oriented Connectionless
Initial setup required not necessary
Destination address only needed during initial setup needed every packet
Packet sequencing guaranteed not guaranteed
Option negotiation possible at setup not available
Overhead moderate low


Retransmission Protocols

All packets have a sequence number and a CRC.

Sender saves the packets that were sent. When the receiver gets a valid packet with the correct sequence number, it sends an ACKnowledgment to the sender. If it gets an invalid packet, it can (optionally) send a negative acknowledgment (NAK) to the sender. When the sender gets an ACK, it can discard the sent packets. If it gets a NAK or nothing (time-out), it can resend the packets.

The Time-out has to be carefully set. If too short, packets will be unnecessarily resent before an ACK can arrive. If too long, the system will pause when a packet is lost.

Notes on Internet Routing and Datagrams

Internet addresses cannot be used by the hardware. The network hardware uses its own hardware addresses. The data portion of a hardware packet contains the Internet header and the data.

IP packet header

The packet contains the Internet address of both the source and destination. The type field specifies the transport level protocol to be used (i.e. TCP or UDP).

When a host needs to send a packet, it separates the netid from the address. If the netid is the same as its own, then it must directly send the packet to the destination using the hardware address of the destination. If the netid is different, it looks in a table to determine what router to send the packet. The packet must be sent to the router using the router’s hardware address.

Netids can be separated from the IP address by ANDing the address with a mask.

The Internet Protocol does not guarantee delivery of packets. It uses Best-Effort delivery, so packets may be: