A gossip algorithm is one in which each computer or device in a network transmits information that it has received from other computers or devices, in order to develop a global agreement on some sort of state.

This is a link-layer algorithm, and link-layer routing (called switching).

The bridges in a network agree on a spanning tree for switching purposes.

What is a tree?
What is a spanning tree?
How can you find a spanning tree?

Here's how bridges find a spanning tree:

The algorithm operates in rounds, occurring every 2 seconds (default).

Each bridge maintains some data: its ID, the spanning tree root, the port to the spanning tree root, and its distance to the spanning tree root.
Every round, the bridge sends a "Bridge Protocol Data Unit (BPDU)" containing a root id, a bridge id (of the sending bridge), a distance to the root, and some other things that we'll ignore.
If a bridge receives a bpdu that contains a "better" root than the current root (usually, a smaller root id), it updates its root, port to the root, and distance to the root.
This continues for a configured number of rounds (default 7), and then all bridges should agree on the root.

Algorhyme

I think that I shall never see
A graph more lovely than a tree.
A tree whose crucial property
Is loop-free connectivity.
A tree that must be sure to span
So packets can reach every LAN.
First, the root must be selected.
By ID, it is elected.
Least-cost paths from root are traced.
In the tree, these paths are placed.
A mesh is made by folks like me,
Then bridges find a spanning tree.

óRadia Perlman

Routers in a network agree on the paths to use to go from one device on a network to another.

This is a network (or Internet) layer algorithm.

Simplest routing protocol, called Bellman-Ford:

Initially, each router knows what networks it has interfaces to and who its neighbors are. It sets up a "distance vector" describing its knowledge of the Internet, that is, the distance vector maps networks to interfaces and distances. For example, this is the Internet looks from my computer (whose interaction with the network is similar to a router's).

192.168.1.0 -> en1, 0: The network 192.168.1.0 is a distance of 0 on interface en1 148.84.38.0 -> en0, 0: The network 148.84.38.0 is a distance of 0 on interface en0

One of the differences between a computer and a router is that a router exchanges what it knows about the Internet with other routers. In the case of Bellman-Ford, it sends its distance vector every few seconds to all of its immediate neighbors. Similarly, it receives distance vectors every few seconds. Each time it receives a distance vector, it updates its own distance vector if it sees a hitherto unknown network (it adds it to its distance vector, along with the interface that received the distance vector message and 1 more than the distance) or if it sees a shorter path to a known network (then it updates the information for the known network).

Ultimately, each router will have a table that tells it the shortest distance to each accessible network and the interface to use to start on the path. When it wants to send a message to a network, it puts it out the proper interface. When the next router receives the message, it uses its own routing table to determine the interface to use to get to the shortest path. And so on, until the message arrives at the right network.

What is reliability?
How can you achieve reliability?

To recover from bit errors in messages, a standard function is used to compute checksum from the bits in a message by the sender. The resulting checksum is sent with the message. The receiver uses the same function to re-compute the checksum. If none of the message bits were changed in transmission, the two checksums will be the same. However, if the two checksums are different, there is an error in the message.

An erroneous message can either be corrected (if the function provided an error-correcting checksum) or re-sent.

For re-sending, either the sender can request the specific message, or an ARQ scheme can be used (ARQ means Automatic Repeat reQuest). For ARQ, the receiver acknowledges every correctly-received message. If an acknowledgment is not received, the sender re-sends the message.

Notice that ARQ works for both lost messages and bit errors.

ARQ is often used on a packet level by link layer protocols.

TCP is a stream-oriented protocol, meaning that from the TCP user's point of view, TCP is transmitting a stream of bytes, not packets. Thus TCP uses a byte-oriented ARQ.

Transmitting bytes individually would be prohibitively expensive, so TCP breaks the stream into units called segments. You can think of a segment as a transport-layer packet. It sends a segment at a time, and looks for cumulative acknowledgments -- that is, when the receiving side acknowledges bytes, it always acknowledges the last byte in a contiguous stream of bytes.

tcpdump is a command-line tool that comes with Unix. It allows you to look at all data on any networks connected to which the computer running tcpdump. Wireshark is a GUI tool that does the same thing. Wireshark can be downloaded from wireshark.org. There are versions for Windows and OS X at the Web site; you can use apt-get to get Wireshark for Ubuntu.

On OS X, you usually have to change the ownership or permissions of /dev/bp* to get access to your interfaces through Wireshark.

Exercises:

1. Look up ARP (Address Resolution Protocol); then select ARP in the Wireshark Filter, and try accessing other computers to see what happens.
   The top window gives you a message summary. What can you learn from that?
   The middle window gives you the individual layers in the message. The basic display is a summary of the header for the layer, starting from the lowest (outermost in the packet), but you can hit the arrow at the left to open up the header.
   The bottom window shows you the actual bytes in the message.
2. Filter on TCP. Try accessing a Web page. What do you see? If you're getting too much TCP stuff, try filtering on HTTP.
3. Filter on your own IP address to ignore other computers; or pick another computer to monitor.

nmap will "scan" a network by sending messages to each host on the network to determine which ports are open, and with certain options, what software is running on each port.

It is a basic tool for both network administrators trying to protect a network and for hackers trying to break into a network.

Using this tool on the wrong network can get you into big trouble.