PackageSwitch

Speed of Network

Predecessor of Package Switching

Circuit Switching

• used in telephone system
• Each phone call has unique connection(physcial wire) that doesn’t shared with others

Problems

• Inefficient, computer communication tend to be bursty
• Diverse rate, different application diff a lot in speed requirement, for example ssh vs video
• State management

Package Switching

• The router can only route exactly one package at any given time, so other packages must be buffered
• No state need to be managed, all communication share the whole link

Definitions

Propagation speed is how fast can the link transmit a bit

Data rate is how fast can we put bits on the link(how many bits can we put on the link per second)

Propagation Delay

• The propagation speed is about 80% of the speed of light, so we use $c$ to represent the speed

• The propagation speed is defined by the material of the link rather then the data rate of the link

Packetization Delay

• The data rate of the link is $r$, the total bits need to be transmitted is $p$
• Do not affected by propagation speed or the distance

End to end Delay

• sum of propagation delay and packetization delay

• Why it is addition here rather than multiplication?

• Sending bits is the link’s job, putting bits on link is the host’s job, they can be done simultaneously.
• Bits can be sent simultaneously, the link do not need to wait for the previous bit to arrive before sending the next one.

Queue Delay

• Your package will be buffered if other package’s arrival is ahead of yours, you have to wait

• Why $Q(t)$ is a function of time ? Because we don’t know at which time the network will become crowded and make you package wait.

• Due to the queueing(UK style of spelling here) delay, the end-to-end delay is unpredictable

$ ping www.stanford.edu
PING pantheon-systems.map.fastly.net (151.101.230.133): 56 data bytes
64 bytes from 151.101.230.133: icmp_seq=0 ttl=52 time=107.877 ms
64 bytes from 151.101.230.133: icmp_seq=1 ttl=52 time=116.139 ms
64 bytes from 151.101.230.133: icmp_seq=2 ttl=52 time=117.227 ms
64 bytes from 151.101.230.133: icmp_seq=3 ttl=52 time=115.867 ms
64 bytes from 151.101.230.133: icmp_seq=4 ttl=52 time=106.592 ms
....

The time varies between each package, it is the round-trip time(sum of to and back)

• Video applications can set a playback buffer to absorb the queueing delay

Queue model

$$
Q(t) = A(t) - D(t)
$$

$$
delay(t) = D^{-1}(bytes) - A^{-1}(bytes)
$$

Why we use package switching

Statistical Multiplexing

Queueing Theory

• Burstiness increase delay

• Little’ result

• Poisson’ process

….

Switching and forwarding

---

---

Ethernet switcher

The forwarding table store hash value of destination address and the matching process is fully matching, that is to say, the addresses must be exactly the same.

class EthernetSwitcher():
    def process(self,package):
        # 1 examine header
        header = getheader(package)
        # 2 if in forwarding table, forward
        if header.destination_addr in self.forwarding_table:
        send(package,self.forwarding_table[hash(header.destination_addr)])
        # if not in forwarding table, broadcast
        else:
            send(package, all_ports)
        # 3 learn from source
        self.forwarding_table[hash(header.source_addr)] = package.from_which_link

Internet router

Virtual Output Queue

Problem with single queue

Pre-categoried strategy