Flow control: end-to-end mechanism for regulating traffic between source and destination Congestion control: Mechanism used by the network to limit congestion The two are not really separable, and I will refer to both as flow control In either case, both amount to mechanisms for limiting the amount of traffic entering the network Sometimes the load is more than the network can handle Eytan Modiano

Optimal Routing View routing as\global\ optimization problem Assumptions: The cost of using a link is a function of the flow on that link The total network cost is the sum of the link costs The required traffic rate between each source-destination pair is known in advance Traffic between source-destination pair can be split along multiple paths with infinite precision

A packet switch consists of a routing engine(table look-up), a switch scheduler, and a switch fabric. The routing engine looks-up the packet address in a routing table and determines which output port to send the packet. Packet is tagged with port number The switch uses the tag to send the packet to the proper output port Eytan Modiano

Carrier Sense Multiple Access(CSMA) In certain situations nodes can hear each other by listening to the channel “Carrier Sensing CSMA: Polite version of Aloha Nodes listen to the channel before they start transmission Channel idle=> Transmit Channel busy = Wait (join backlog) When do backlogged nodes transmit? When channel becomes idle backlogged nodes attempt transmission with probability q=1 Persistent protocol, q=1 Non-persistent protocol,< 1

Broadcast Routing Route a packet from a source to all nodes in the network Possible solutions: Flooding: Each node sends packet on all outgoing links Discard packets received a second time Spanning Tree Routing: Send packet along a tree that includes all of the nodes in the network

Multiple Access shared transmission medium a receiver can hear multiple transmitters a transmitter can be heard by multiple receivers the major problem with multi-access is allocating the channel between the users the nodes do not know when the other nodes have data to send Need to coordinate transmissions

RESERVATION SYSTEMS Single channel shared by multiple users Only one user can use the channel at a time Need to coordinate transmissions between users Polling systems Polling station polls the users in order Polling to see if they have something to send station A scheduler ca

An interesting property of an M/M/ 1 queue, which greatly simplifies combining these queues into a network, is the surprising fact that the output of an M/M/ queue with arrival rate is a Poisson process of rate This is part of Burke's theorem, which follows from reversibility A Markov chain has the property that P[future present, past] P[future present] Conditional on the present state, future states and past states are independent

Queueing Systems Used for analyzing network performance In packet networks, events are random Random packet arrivals Random packet lengths While at the physical layer we were concerned with bit-error-rate, at the network layer we care about delays How long does a packet spend waiting in buffers

Service times Poisson arrivals at rate n Service time has arbitrary distribution with given E[X] and E[X2I Service times are independent and identically distributed (ID) Independent of arrival times E[service time]=1/u Single Server queue