Computer Networking

Bandwidth is a term frequently used for Throughput or Bit Rate in the context of networks (instead of the width of a frequency band in the context of transmissions). Example: Bandwidth-Delay Product that corresponds in fact to Throughput-Delay Product.

Bit Rate is mostly used to provide the information on the raw transmission capacity at the PHY layer while Throughput refers to the transmission capacity at upper layers: e.g. useful throughput at TCP = the number of bits transferred over a TCP connection per unit time.

To compute delay (or latency):

\(d = t_p + t_t + t_w\), where

\(d\) is the delay, \(t_p\) propagation time, \(t_t\) transmission time, and \(t_w\) waiting time (usually neglected).

\(t_p = l/v\), where

$l$is the distance and \(v\) is the speed of signal propagation:

\(v = 2.3 \times 10^8 m/s\) for copper \(v = 2 \times 10^8 m/s\) for glass (fibers) \(v = 3 \times 10^8 m/s\), speed of light in vacuum (satellites)

A useful rule of thumb for computing the propagation time is \(5 \mu s\) per km, e.g. the propagation time for the distance of 10000 km is 50 ms.

\(t_t = s/r\), where \(s\) is the number of bits to transmit and \(r\) is the bit rate.

Bandwidth-Delay Product is defined as:

\(\beta = C \times RTT\) \([bits]\),

where \(C\) is the bit rate (or throughput or capacity in b/s) and \(RTT\) is the Round Trip Time. It corresponds to the maximum amount of data that can be sent on a link or a network before receiving an acknowledgment ("the number of bits to fill the pipe").

If the sender can send a sufficient amount of data compared to the bandwidth-delay product, then the utilization of the link (or the network) is high and the transfer protocol achieves good performance.

Example: 129.88.30.11 and 129.88.30.12 are two Internet hosts on a subnetwork identified by 129.88.30 11 and 12 are host identifiers.

A CIDR prefix designates a block of IP addresses by indicating the first address of the block and its length, which corresponds to the length of the field used for identifying hosts on a sub-network (IPv4 : 32 - prefix length, IPv6 : 128 - prefix length).

Exemple :

• 129.88.30/24 represents a block of 256 addresses (\(2^8\), \(8 = 32 - 24\)) starting at 129.88.30.0.
• 129.88.30/23 represents a block of 512 addresses (\(2^9\), \(9 = 32 - 23\)) starting at 129.88.30.0.

CIDR allows aggregation of address blocks: e.g. blocks 129.88.30/24 and 129.88.31/24 can be represented as one 129.88.30/23 block.

Assume that the network needs to maintain the information on how to route packets to subnetworks 129.88.30/24 and 129.88.31/24 (the information on the next-hop router used for forwarding packets to the sub-networks). Instead of handling two routing entries of 129.88.30 and 129.88.31, the network can aggregate them into one prefix 129.88.30/23 and handle only one entry in routing tables. In this way, routers need to know about less routes.

A netmask is a 32 bit word with \(n\) high-order bits set to 1. Netmasks are represented in dotted decimal notation like addresses: e.g. 255.255.255.0 corresponds to /24 prefix.

The prefix results from applying AND bitwise operation to the address and the netmask. Example: 129.88.30.11 AND b11111111111111111111111100000000 gives 129.88.30.00 that corresponds to prefix 129.88.30/24.

When assigning addresses to hosts on a subnetwork, we need to take into account two addresses that are not useable for hosts (subnetId.all 1 and subnetId.all 0). A router connected to a given subnetwork will also need an address within the subnetwork (by convention, we assign high numbers to routers and low numbers to hosts).

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination address | Netmask         | IP address of Next Hop  |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 0.0.0.0             | 0.0.0.0         | 129.88.30.254           |
| destinationAddr1    | 255.255.255.000 | 129.88.30.254           |
| destinationAddr2    | 255.255.255.000 | 129.88.48.254           |

We can interpret the information in the table as follows: if the destination address of the packet matches the destination address or prefix in the table, forward the packet to Next Hop.

The first entry in the table is called DEFAULT: it matches any destination.

You can inspect the table with a command such as netstat on Unix or route on Windows.

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Interface | IP Address      | Netmask         |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| en0       | 129.88.30.0     | 255.255.255.000 |
| en1       | 129.88.48.0     | 255.255.255.000 |

You can inspect the physical interface table with the command ifconfig on Unix and ipconfig on Windows.

More specifically:

Let destAddr is the address in the packet to forward, destinationAddr is an address in the routing table.

• Case 1: a host route exists for destAddr:
  • for every entry in the routing table
  • if (destinationAddr = =destAddr)
    • then send to Next Hop from the entry; leave
• Case 2: destAddr is on a directly connected subnetwork (= on-link):
  • for every physical interface IP address A and netmask NM
  • if (A & NM = =destAddr & NM)
    • then send directly to destAddr; leave
• Case 3: a network route exists for destAddr:
  • find the longest prefix that matches destAddr in the routing table
  • then send to Next Hop from the entry; leave
• Case 4: use default route:
  • send to Next Hop from the DEFAULT entry; leave

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Version|  IHL  |Type of Service|          Total Length         |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|         Identification        |Flags|      Fragment Offset    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  Time to Live |    Protocol   |         Header Checksum       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                       Source Address                          |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                    Destination Address                        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                    Options                    |    Padding    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Version Number

four bits specifying the IP protocol version of the datagram. Two versions currently coexist: IPv4 and IPv6.

Header Length (IHL)

the packet header may contain a variable number of options so we need the information about the header length. The minimal header without option is 20 bytes.

TOS (Type of Service)

initially specified the requested type of service for the packet: priority (0 - normal, 7 - control packets), short delay (for applications such as telnet), high throughput (FTP), high reliability (SNMP), low cost (NNTP). Currently, the TOS field supports DiffServ (Differentiated Services): 1 byte codepoint defining a QoS (Quality of Service) class: Expedited Forwarding (EF) - minimize delay and jitter, Assured Forwarding (AF) - four classes and three drop-precedence (12 codepoints).

Length

total length of the packet (header and data payload) in bytes. The field on 16 bits allows encoding the theoretical maximum size of 65,535 bytes, but IP packets are usually limited to the maximal size of the link-layer data frame, e.g. if a host is connected to the Ethernet, it will send its packets in a frame limited to 1,500 bytes. Any subnetwork should support transporting packets of the minimal size of 576 bytes (512 bytes of the data payload and 64 bytes of the header, 60 bytes being the size of the maximal header).

Identifier

used in fragmentation. A unique value assigned by the sender to assemble the fragments of a packet.

Flags

used in fragmentation. Values: bit 0 - reserved, must be zero; bit 1: (DF) 0 = May Fragment, 1 = Don't Fragment; bit 2: (MF) 0 = Last Fragment, 1 = More Fragments.

Fragment Offset

used in fragmentation. It indicates where in the packet this fragment belongs. The fragment offset is measured in units of 8 octets (64 bits). The first fragment has offset zero.

Time-To-Live (TTL)

indicates the maximum time the packet is allowed to remain in the Internet. Initially, the time was measured in seconds, currently, each router decreases the TTL by one. If the TTL field reaches 0, the router drops the packet and sends an ICMP packet to the source.

Protocol

indicates the next level protocol that will process the data payload. Example values: 6 - TCP, 17 - UDP (cf. RFC 1700 for all possible numbers).

Header Checksum

checksum on the header only. As some header fields change (e.g. TTL), the checksum is recomputed and verified at each router. The checksum field is the 16 bit one's complement of the one's complement sum of all 16 bit words in the header. For purposes of computing the checksum, the value of the checksum field is zero.

Source and Destination IP Addresses

32-bit IP address of the source and final destination.

Data (payload)

contains the data to be delivered to the next layer protocol at the destination.

• Strict Source Routing: specifies the list of all routers to the destination,
• Loose Source Routing: specifies the list of some routers to the destination,
• Record Route: used to trace the route a packet takes,
• Timestamp Route: used to trace the route a packet takes and the instants of crossing routers,
• Router Alert: alerts transit routers to more closely examine the contents of an IP packet (used by IGMP or RSVP for processing a packet, cf. RFC 2113).

MTU is the maximum amount of data that a link-layer frame can carry. The MTU of a link-layer protocol gives a limit on the length of an IP packet that may cross the link (e.g. 1500 bytes for Ethernet).

When a router want to forward an IP packet over a link with an MTU smaller than the packet size, it needs to fragment the packet: transform a large packet into a series of smaller ones called fragments. The destination reassembles the fragments into the original packet before delivery to the next protocol layer.

Example: a packet of 1400 bytes of data needs to be fragmented before crossing a link with the 620 byte MTU.

L: Length, I: Identification, MF: More Fragment flag, Of: Offset

Initial packet: L= 1420, I=567, MF=0, Of=0

Fragments:

1. L= 620, I=567, MF=1, Of=0
2. L= 620, I=567, MF=1, Of=75 (8*Of=600)
3. L= 220, I=567, MF=0, Of=150 (8*Of=1200)

Based on the information, the destination can reassembly the original packet.

Routes and hosts use the ICMP protocol to report an error in packet processing: a packet cannot reach its destination, when a router drops a packet, or a router can notify a host to send traffic on a shorter route.

ICMP messages are encapsulated in IP packets.

ICMP messages have a type, a code field, and contain the first eight bytes of the IP packet that caused the generation of the ICMP message.

Main ICMP messages:

Type        Code		Description

0           0         Echo Reply (ping)
3           0-15      Destination Unreachable (network, host, protocol, port)
5           0-3       Redirect
8           0         Echo Request (ping)
11          0         Time Exceeded

Other ICMP messages:

Type        Code		Description

9           0         Router Advertisement
10          0         Router Solicitation
12          0         Bad IP Header
13          0         Timestamp
14          0         Timestamp Reply
15          0         Information Request
16          0         Information Reply
17          0         Address Mask Request
18          0         Address Mask Reply

Ping command generates an ICMP Echo Request message to a destination that replies with an ICMP Echo Reply message.

Traceroute command discovers the IP addresses of the intermediate routers towards a destination: Traceroute generates an IP packet with a UDP segment to a destination and sets TTL=1. The first router on the path to the destination decrements TTL that becomes 0 so it drops the packet and sends an ICMP Time Exceeded message to the source. Then, Traceroute generates an IP packet with TTL=2 to discover the second router and so on. The destination replies with an ICMP Destination Unreachable message, because the UDP segment uses a non-existent port number.

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|         Hardware Type         |         Protocol Type         |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  HW@ Length   | Proto@ Length |            Opcode             |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                        Sender Hard...                         |
+                               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|          ware Address         |          Sender Proto...      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|          col Address          |          Target Hard...       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+                               +
|                        ware Address                           |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                    Target Protocol Address                    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

ARP Request sent
Wait for reply
     if received, put target information (MAC address) into the table
 if not, repeat on timeout, increase timeout on each failure

ARP Packet received
If IP address = our address
  put the sender information into the ARP table
      reply with our Ethernet address as target
Otherwise
  if IP address in the table
     update entry
  otherwise
    do not update

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Version| Traffic Class |           Flow Label                  |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|         Payload Length        |  Next Header  |   Hop Limit   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
+                                                               +
|                                                               |
+                         Source Address                        +
|                                                               |
+                                                               +
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
+                                                               +
|                                                               |
+                      Destination Address                      +
|                                                               |
+                                                               +
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

The header of an IPv6 packet has the following fields:

Version Number

four bits specifying the IP protocol version of the datagram.

Traffic Class

QoS on aggregates - the DiffServ 1 byte codepoint.

Flow Label

identifies packets belonging to the same flow, per flow QoS.

Payload Length

length in bytes of the packet payload (data following header).

Next Header

indicates the type of the header immediately following the basic header.

Hop Limit

like TTL - decremented each time the packet is forwarded, packet discarded when it reaches zero.

Source and Destination Addresses

16 byte addresses.

Hop by Hop

must be processed by each node on the path to the destination.

Destination

information for the destination host.

Fragment

similar to IPv4, but only the source may fragment. Packets exceeding the maximal size are dropped by routers and an ICMP message is sent to the source.

Authentication

support of IPSec.

Encapsulating Security Payload

support of IPSec.

Addresses are 16 bytes long = 128 bits, 4 times more bits than in IPv4 (number of addresses: \(3.4 \times 10^{38}\)).

Notation:

• 8 groups of 16 bits in hexadecimal, 4 hex digits separated by ":"
• leading zeros of each group can be ignored
• one group of zeros can be replaced by "::"
• CIDR notation as in IPv4: prefix/len

Examples:

• 2001:660:5301:26:210:83ff:fe35:3404/64
• fe80::210:83ff:fe35:3404
• ::1/128 (loopback)
• 2000::123:4567:89AB:CDEF
• FF05::1:3

Address types and scope:

• unicast as in IPv4,
• anycast: an address shared by several hosts - a packet is sent to the "nearest" host.
• multicast: prefix FF00::/8 (there is no broadcast in IPv6)
• IPv4 addresses in IPv6: IPv4-mapped IPv6 address (::FFFF:<IPv4 address>, e.g. ::FFFF:129.144.52.38)
• link-local: prefix FE80::/10
• global addresses: reachable in the Internet, prefix 2000::/3

Format: 8-bit prefix 11111111 + 4-bit flags + 4-bit scope + 112-bit group ID

• flags: T=1 - permanent address
• scope is a 4-bit value that defines the scope of the multicast group: 1 Interface-Local scope 2 Link-Local scope 4 Admin-Local scope 5 Site-Local scope 8 Organization-Local scope E Global scope.
• examples: FF02::101 - all link-local NTP servers (scope = 2, NTP group = 101), FF02:0:0:0:0:0:0:1 - all link-local nodes.

Solicited-Node Address:

Solicited-Node Address of the form FF02:0:0:0:0:1:FFXX:XXXX is a multicast address computed as a function of a node unicast and anycast addresses.

A Solicited-Node Address is formed by taking the low-order 24 bits of an address (unicast or anycast) and appending those bits to the prefix FF02:0:0:0:0:1:FF00::/104 resulting in a multicast address in the range from FF02:0:0:0:0:1:FF00:0000 to FF02:0:0:0:0:1:FFFF:FFFF. For example:

• the Solicited-Node multicast address corresponding to the IPv6 address 4037::01:800:200E:8C6C is FF02::1:FF0E:8C6C.

Replaces ICMP and ARP of IPv4.

Main ICMPv6 messages:

• Destination unreachable (type 1)
• Packet too big (type 2)
• Time exceeded (type 3)
• Parameter problem (type 4)
• Echo request/reply (type 128 and 129)

Neighbor Discovery:

• Replaces ARP, ICMP (redirect, router discovery)

IPv6 supports autoconfiguration of addresses.

A node creates a link-local address by concatenating the link-local prefix FE80::/10 and a unique 64-bit EUI-64 (Extended Unique Identifier) IPv6 interface identifier. EUI-64 is obtained from the 48-bit MAC address: the MAC address is first separated into two 24-bit parts. The 16-bit 0xFFFE pattern is then inserted between these two 24-bit parts to form the EUI-64 identifier. Finally, the seventh bit from the left (the universal/local, U/L bit), needs to be inverted.

• Example of EUI-64:
  1. Ethernet address on 48 bits: 00:90:27:17:FC:0F
  2. EUI-64 on 64 bits, 7th bit inversed: 02:90:27:FF:FE:17:FC:0F
• Example of the created link-local address: FE80::290:27FF:FE17:FC0F

• To obtain a global routable address, a node needs to learn its prefix using Router Solicitation and Advertisement. We assume that there is a router connected to the same link as the node.
• At boot time, a node has to join 2 special multicast groups for each network interface:
  • All-nodes multicast group: ff02::1
  • Solicited-Node multicast group: ff02::1:ffXX:XXXX, XX:XXXX come from the lower 24 bits of the node address
• When node A needs to learn the prefix, it sends:

ICMP Type = 133 (Router Solicitation), Src = link-local address, Dst =
all-routers multicast address (=FF02::2=), Query = Please send RA

Router responds with an ICMPv6 packet to all nodes on-link:

ICMP Type = 134 (Router Advertisment), Src = link-local address, Dst =
all-nodes multicast address (FF02::1), Data = options, subnet prefix,
lifetime

Example: if the prefix is 2001:660:5301::/48, the global routable address is 2001:660:5301::290:27FF:FE17:FC0F.

Neighbor Solicitation (ICMPv6 type 135) and Neighbor Advertisement (ICMPv6 type 136) replace ARP.

To find the MAC address of neighbor B, host A sends an ICMPv6 packet:

ICMP Type = 135 (Neighbor Solicitation), Src = A, Dst = Solicited-Node
multicast of B, Data = link-layer address of A, Query = what is your link
address?

B responds with an ICMPv6 packet:

ICMP Type = 136 (Neighbor Advertisement), Src = B, Dst = A, Data =
link-layer address of B

When a node creates its link-local address, it needs to verify that it is unique by sending a Neighbor Solicitation packet to the Solicited-Node multicast corresponding to the link-local address. If there is no response, the address is unique.

• Example: if the node creates the link-local address FE80::290:27FF:FE17:FC0F, the corresponding solicited-node multicast is FF02::1:FE17:FC0F.

1. Initialization: PATH variable: router A (the best paths to destinations) TENT variable: empty (tentative paths)
2. For each router \(N\) in PATH for each neighbor \(M\) of \(N\)

   \(c(A, M) = c(A, N) + c(N, M)\) if \(M\) is not in PATH nor in TENT with a better cost, insert \(M\) with direction \(N\) in TENT

3. If TENT is empty, end. Otherwise take the entry with the best cost from TENT, insert it into PATH and go to 2.

At the end, PATH contains the tree of best paths to all destinations: the next hop and the shortest distance to all destinations.

The topology is in the form of bus segments (coaxial cable): one backbone segment connected to other segments. The cable provides the shared transmission medium of the nominal throughput of 10 Mb/s that supports broadcast: a frame sent by one device will propagate over the cable to reach all other connected devices, which means that all stations receive all transmitted frames and copy to their buffers only the frames sent to them. To extend the coverage, repeaters between segments amplify the signal and retransmit on another segment. There are limitations on the segment length, the number of repeaters, and the topology that bound the total round trip time between any two stations connected to the network to \(51.2 \mu s\).

n = 0
repeat
	wait until carrier sense off
	wait for interframe gap
	transmit and detect collision
	if (collision detected) then 
	   stop transmitting 
	   transmit jam (32 bits)
	   n++
	if (n == maxAttempts) then
	   abort
	k = min(n, 10)
	r = random(2^k - 1)
	wait for random time (r × slotTime)
	else
		success
until (success or abort)

A station that wants to transmits, tests if the channel is already used (carrier sense on). If the channel is free, the station waits for an interval called interframe gap (\(9.6\mu s\)) and transmits the frame. While transmitting, it checks whether a collision happens (by detecting an increased power of the signal on the cable due to overlapped transmissions). In case of a collision (collision detected), the station stops transmitting the frame and transmits a sequence of random bits called a jam (32 bits). Then, it increments \(n\), the counter of collisions and chooses a random retransmission interval:

\(T = r \times slotTime\),

where \(r = random(2^k - 1)\), \(k = min (n, 10)\), and \(slotTime = 51.2 \mu s\).

Value \(r\) for subsequent collisions is the following:

• 1st collision, \(r \in [0, 1]\)
• 2nd collision, \(r \in [0, 3]\)
• 10th, \(r \in [0, 1023]\)
• 15th, stop

Another collision may happen if both stations choose the same value of \(r\), which arrives with probability \(1/2\) for the first collision, \(1/4\) for the second one, and then \(1/2^k\).

Increasing the interval for choosing \(r\) in the exponential way is called exponential backoff.

The station retransmits the frame after the retransmission interval (it follows the rules for accessing the channel: detecting channel activity, deferring until the channel is free, and eventually, waiting for an interframe gap).

The figure illustrates how a collision is recovered:

• at time \(t=0\), both stations \(A\) and \(C\) have frames to send, they test the channel and start sending their frames, because there is no on-going transmission at this instant
• at time \(t=T_p\), when the signal of \(A\) arrives at \(C\) (and the signal of \(C\) at \(A\)) both stations detect a collision, stop their transmissions and send a jam
• after the jam, they choose random retransmission intervals:
  • \(A\) chooses 1 slotTime, it defers the retransmission
  • \(C\) chooses 0 slotTime, it can proceed
• \(C\) tests the channel (there is still the signal corresponding to the jam of \(A\)), waits until there is no signal and send its frame
• when \(A\) tests the channel after 1 slotTime, but there is the on-going transmission of \(C\), so it waits until the end of the frame
• \(A\) transmits after the end of the frame of \(C\) (not shown in the figure).

slotTime of \(51.2 \mu s\) guarantees that after this time, all stations receive the transmitted signal and they do not interfere with the current transmission (collisions may not happen after this interval). The value of \(51.2 \mu s\) comes from the limitation of the segment length and the maximal number of repeaters between any two stations: all the propagation delays result in a round trip time less than \(51.2 \mu s\), the value that corresponds to the transmission of 64 Bytes over 10 Mb/s. This parameter results in:

• \(51.2 \mu s\) becomes the retransmission unit: if after a collision, a station tries to retransmit after \(51.2 \mu s\), either the channel is free et it transmits, either there is ongoing transmission, so it will defer until its end (we avoid another collision),
• if a station has already sent 64 Bytes, the channel is acquired by the station–there will be no collision during the transmission,
• if there is a collision, the rest of the unsuccessful transmission will have the size < 64 Bytes. Any frame with the size < 64 Bytes is invalid.

Ethernet 2 encapsulation:

 0                   1
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|           DST_ADDR            |
|          (6 octets)           |
|                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|            SRC_ADDR           |
|          (6 octets)           |
|                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    ETHER_TYPE  (2 octets)     |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
~                               ~
~           payload             ~
~       (46 - 1500 octets)      ~
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|      CHECKSUM (4 octets)      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

The DST_ADDR field contains either a unicast address or a group address (the first bit of the address = 1).

Data on Ethernet are transmitted least significant bit of the first byte first (a bug of Intel processors). Canonical representation thus inverts the order of bits inside a byte (the first bit of the address is the least significant bit of the first byte).

Addresses are represented in the hex notation: 08:00:20:71:0d:d4. The broadcast address is ff:ff:ff:ff:ff:ff.

Exemples :

• a group address: 01:00:5e:02:a6:cf.
• a multicast address for IPv4: 01:00:5e:02:a6:cf.
• a multicast address for IPv6: 33:33:ff:02:a6:cf.

  ETHER_TYPE determines an upper layer protocol that will interpret the payload: 0x0800 (IPv4), 0x86DD (IPv6), 0x08060 (ARP).

Fast Ethernet: 100 Mb/s over 4 twisted pairs.

Gigabit Ethernet: 1 Gb/s, 10Gb/s, 40 Gb/s over fiber.

Advanced cabling with twisted pair cables: interconnection with hubs - multiport repeaters - a Layer 1 interconnection element.

A hub receives a signal and retransmits it on all outgoing ports.

Full-duplex Ethernet: possibility of sending and receiving at the same time. No collisions possible.

The problem of which port to choose for a destination address that is not yet in the forwarding table, is solved with flooding: when there is no entry in the forwarding table, the switch will replicate the frame and send the frames on all outgoing ports. Flooding solves the initialization problem, but suffers from the possibility of creating an increasing number of frames if the topology of switch (or bridge) interconnection contains a loop.

Simple case - low load, no channel activity:

test the channel
if free, 
   wait DIFS interval (long),
   if the channel free
      transmit frame
      wait SIFS interval (short)
      receive ACK

More complex case with contention of at least two stations - there is channel activity, apply Collision Avoidance: choose a random wait interval before transmission attempts:

Residual = 0

Start: 
if channel used,
   n = 0
   wait until carrier sense off, 
   wait DIFS interval (long)
   if the channel free
      if Residual > 0
         wait Residual
	 otherwise
         choose backoff r from Contention Window [0, Wmax]
         wait r x Slot
         if receives a transmission signal
            stop waiting, Residual = remaining Slots, go to Start:
	    otherwise
            transmit frame
            wait SIFS interval (short)
            receive ACK

CSMA/CA and preamble/header overhead make the useful throughput fairly low compared to the nominal bit rate: around 60% of 11Mb/s - 6.5Mb/s at application layer.

The current sending window \(W\) is modulated by the congestion control algorithms through \(cwnd\) or flow control through \(rwnd\) (remember that \(rwnd\), the Receive Window in octets contains the window advertised by the TCP receiver corresponding to the free buffer space):

• \(W = min (cwnd, rwnd)\).

In the examples of Congestion Control, we assume that \(rwnd\) is sufficiently large so \(cwnd\) limits \(W\).

From the congestion control point of view, TCP evolved over time. Several variants have been defined: Tahoe, Reno, New Reno, Vegas. More recent variants include: BIC, CUBIC, Compound, and many more. Tahoe is the simplest variant with two states: Slow Start and Congestion Avoidance. Reno adds Fast Recovery.

ssthresh = 64KB
cwnd = 1 * MSS (initial value depends on implementation and it may go up to 3 MSS)
increase cwnd by 1 MSS for each received ACK, which results in exponential
increase: 1, 2, 4, 8 MSS etc.

if packet loss on timeout, apply Multiplicative Decrease:
   ssthresh = cwnd / 2 (but not less than 2MSS) 
     reenter Slow Start

if cwnd >= sshtresh, enter Congestion Avoidance

ssthresh corresponds to the threshold that a TCP source tries to attain: TCP probes for the bottleneck capacity by progressively increasing the congestion window until:

• a loss - reenter Slow Start or
• cwnd >= sshtresh, enter Congestion Avoidance.