Digi Comms 2

The telephone network: Designed to carry voice. Uses digital samples internally. Low end-end delay. Basic two-way voice. Hierarchically allocated telephone number space.

End systems: Most end systems are analogue, with microphones and speakers (transducers). Circuits are shared to avoid having to use 4 wires but leads to sidetone (local) and echo (far end) though. Dialing can be done by pulse (a pulse per unary coded digit) or tone (pair of tones on 4*3 grid =12 digits).

Transmission: Links have different bandwidth (range of frequencies/information capacity), delay (time for signal to reach other end) and attenuation (need repeaters). Multiplexing: Analog (band limit call and frequency shift), digital. If a trunk carries bits at a faster rater than inputs can do time division multiplexing by interleaving. Can transmit through geosynchronous or nongeosynchronous satellites (complicated hand off though).

Switches: Any user could potentially call any other user, but cant have direct lines. Switching establishes temporary circuits. Space division multiplexing:

Also can do time division interchange, but need a schedule:

Signaling: Every switching system has a switch controller. The switch controller is in the control plane, and performs actions such as call routing, alarms, billing and directory lookup. They are linked by their own internal computing network.

Cellular Communication: Mobiles talk to a base station, aren't enough frequencies to give each mobile a permanent frequency. So reuse, both temporal (when turned off, no frequency assigned) and spatial (mobiles in non adjacent cells can use the same frequency). On power on a mobile tells the base of its ID and home. Need to hand off between base stations.

The Internet:

Intranets: are administered by a single entity eg a University. Internet is administered by a coalition of entities. Extranets are privileged intranet services made available to exterior customers, eg website with passwords.

Packets: Self descriptive data, ie data + data. They can be stored and forwarded due to this meta data.

Addressing: Internet addresses are called IP addresses. They refer to a host interface: need one ip per interface. Structured as network number (eg 125.105.53) and host number (eg 100).

Address classing: Class A has 8 bits network and leading bit 0, 24 bits host, class b has 16 bits network and 16 host and leading bits 10, class c has 24 bits network and 8 bits host and leading bits 110. Addresses can be associated with a mask that indicates the partition point.

Routing: How to get to a destination given its ip. Need to compute the routing table (which tells us the next hop). Generally works by keeping detailed routes for the local neighborhood and a default router for unknown destinations. More optimal paths, bigger routing tables. Ip is designed to have a dumb network, with clever end points. TCP is used to deal with network defects. Decentralization (no yellow pages, hard billing, no guarantees) and ip address shortage are both major problems.

ATM Networks

ATM networks: Designed to have benefits of the Internet (flexible and cheap) with those of the telephone networks (quality of service guarantees). Badly designed but used in ADSL. Use virtual circuits, fixed size packets, small packet size, statistical multiplexing and integreated services.

Virtual circuits: Under telephone network synchronous transmission mode is used (the destination of a sample depends on where it came from, and when). However, idle users consume bandwidth and you can't dial bandwidth. Virtual circuits use packets, which carry only identifiers rather than full addresses [VCI][Data]. VCI's save header space, but need to be set up and translated at intermediate points. All packets must follow the same path, and there needs to be a setup phase before transfer can begin. This can be reduced by preallocating a range of VCI's.

Fixed size packets: Simpler buffer hardware, simpler line scheduling, cheaper switches. Overhead for sending small amounts of data, segmentation and reassembly cost, last unfilled cell wastes bandwidth.

Small packet size: Smaller the packet, smaller the packetization delay but higher header overhead. Normally 48 bytes + 5 byte header.

Statistical multiplexing: Trades worst case delay for output trunk speed, and service rate for delay. If a resource has capacity C, and is shared by N identical tasks each requiring capacity c and Nc <= C then the resource is underloaded. There are two types of statistical multiplexing: spatial (only a fraction of tasks are active simultaneously) and temporal (a task is only active part of the time). Eg say you have a 100 room hotel, how many external phone lines does it need? Both spatial and temporal statistical multiplexing gain.

Integrated service: Can do void, video, data all on one network. Allows for this through signalling, scheduling, high bandwidth, reservations.

Mixing IP and ATM: Difficult, connectionless vs connection orientated, best effort vs resource reservation, quality of service, different routing protocols.

Protocol layering:

Protocol: A set of rules and formates that govern the communication between communicating peers. Tells us syntax, semantics and action to take on messages. Protocols may use other protocols, eg file transfer protocol uses packet transfer protocols. This dependency is called layering. Layering splits problems into manageable pieces, allowing reuse of functionality. Greater abstraction (information hiding), lower performance.

Service access point: Interface between an upper layer and a lower layer.

Protocol data units: Packets exchanged between peer entities. Eg Letter. PDU = SDU + optional header.

Service data units: Packets handed to a layer by an upper layer.

OSI Reference Model:

• The physical layer is responsible for moving information between two systems, and describes things such as the coding scheme used to represent a bit on a communication link.

• The datalink layer involves in particular framing packets so the system can distinguish packets from random noise. The medium access control sublayer, which controls addressing on broadcast LANs, is a sublayer of the datalink layer.

• The network layer is involved with the concatenation of sets of links to make them appear act as end-to-end links. In data-gram networks the is a separate control and data plane, where the control plane deals with the network.

• The transport layer uses the abstraction of the network layer to provide an error and flow controlled end-to-end link.

• The session layer is used in some systems to provide a bidirectional service and atomic data transmission.

• The presentation layer deals with the presentation of the actual data (whereas most of the above layers deal with the meta-data). For example some systems may store big endian, others little endian, and this layer may convert from one to the other.

• This application layer is the name given to the set of applications running on networks systems.

System design: Maximize some resource metrics given constraints. Common resources involve time (seconds), space (kilobytes), computation, money, labor, social constraints, scaling. A bottleneck is the most constrained element in a system, removing it improves performance but new bottlenecks appear.

Pipelines: If sum of times taken by all stages =R, slowest stage takes time S. Throughput = 1/S, response time =R, degree of parallelism =R/S. Maximum parallelism when R/S=N.

Batching: Grouping tasks together to amortize overhead.

Optimizing the common case: Amdahls law, 80% of the time is spent in 20% of the code.

Hierarchy: Recursively splitting a system into smaller pieces makes it more scalable.

Binding and indirection: Abstraction is good, allows generality of description.

Virtualization: Refer to a virtual resource that gets matched to an instance at run time.

Randomization: Good way of resolving contention fairly

Soft state: Memory in the system that influences future behavior eg VCI translation table.

Hysterisis: System changes state depending on whether a variable is above/below a threshold.

Naming and addressing:

Names: denote something and are generally for humans. Addresses denote where something is and are machine understandable. A route tells you how to get to an address. Binding is the process of linking names to addressees, addresses to routes, addresses to hosts etc.

Hierarchical naming: Naively ask a naming authority if the name you're proposing is unique. Instead recursively decompose the name space into mutually exclusive portions (zone delegation).

Domain name service: A name server is responsible for a set of domains. May delegate to children. If local server can't answer a query, it asks root which delegates reply. Eg ask root name server who knows about .uk domain, then ask who knows about .ac, then ask who knows about .cam etc. DNS records can map DNS names to IP addresses, can also do things such as email handling and reverse DNS.

Addressing: Need to be hierarchical to ensure globally unique, and to reduce the size of routing tables at the expense of longer routes. Ipv4's functional lifetime has been extended through subnetting (allows administrator to cluster IP addresses within a network, not visible outside the network), classless inter domain routing (allows contiguous class C blocks to be refereed to as larger an address block using a CIDR mask but requires that all routers agree to use it), dynamic host configuration and network address translation.

Dynamic Host Configuration: Allows a set of hosts to share a pool of IP addresses. A newly booted computer broadcasts discover to subnet. The DHCP servers reply with offers of IP addresses. The host picks one and broadcasts a request to a particular server. All other servers withdraw offers, and selected server sends an ack. When done, the host sends a release. IP address has a lease which limits time it is valid. The server reuses IP addresses if their lease is over.

Network Address Translation: Aggregates multiple IP addresses behind one IP address.

Ipv6: Extends address space from 32bits to 128 bits. Classless addresses, multiple levels of aggregation (registry, provider, subscriber, subnet), multicast.

ATM Network addressing: Network Service Access Point addresses, variable length with several levels of hierarchy.

LAN: Need to know MAC or ethernet addresses from datalink layer when going into network.

Routing:

Routing: The process of finding a path from a source to every destination in the network. It is the binding of addresses to paths. A routing protocol sets up a routing table in routers and switch controllers. A node makes a local choice on global topology. Want to minimize routing table, reduce exchanges with peers. Choices involve centralized vs distributed routing (centralized is simpler, but prone to failure and congestion). Source based vs hop-by-hop (how much to place in the packet header? Middle way is loose source routing). Stochastic vs deterministic (stochastic spreads load but misorders). Single vs multiple path. State-dependent vs state-independent.

Routing in telephone networks: DNHR, TMSR and real time.

Dynamic Non-Hierarchical Routing: The simplest core routing protocol, it accepts a call if a one hop path is available otherwise it is dropped. The day is divided into about 10 periods, at each period each toll switch is assigned a primary path and a list of overflow alternatives. Bursts of activity can cause the network to enter a metastable state.

Trunk map status map routing: Dynamic non hierarchical routing measures traffic once a week.

Real time network routing: No centralized control, each toll switch maintains a list of lightly loaded links. The intersection of source and destination lists gives a set of lightly loaded paths. Very effective.

Other routing: In a distance vector algorithm a node tells its neighbors its distance to every other node in the network, and in a link state algorithm a node tells every other node in the network its distance to its neighbors.

Distance Vector: Tells its neighbors the distance to every other node in the network. Each router maintains a distance vector, a list of <destination,cost> tuples where cost is the sum of the link costs on the shortest paths. If a lower cost is received the tuple is updated. A router periodically sends a copy of its distance vector to all its neighbors. Link state routing protocols are designed to operate in large networks, and are more complex and can take into account costs such as bandwidth. Link state convergence occurs faster than distance vector convergence as it establishes a neighbor relationship with directly connected peers and shares routing information with its neighbors only when there are changes in the network topology. Link state routing protocols only send updates to neighboring routers, rather than sending an entire routing table and so are more scalable. Distance vector can suffer from count to infinity when a link goes down and two nodes both think they can get to the old destination through each other. Split horizon: never tell neighbor cost to X if neighbor is next hop to X.

Link state routing: Distributes the topology of the network and the cost of each link to all the routers, each router independently computes optimal paths to every destination. A router describes its neighbors with a link state packet, use controlled flooding to distribute this everywhere. A sequence number in the header shows if an LSP is new. The creator of the LSP puts a timeout value in the header, the router removes LSP when it times out. If a router gets an older LSP it tells the sender about the newer LSP, so newly booted router quickly finds out its most recent sequence number.

Routers: Failure can be detected by using periodic hello packets. Routers databases must be protected with checksums and passwords. Can use dijkstra's algorithm to compute shortest path: find every way to get to a node, choose shortest one.

Choosing link costs: Could set all link costs to 1, but this doesn't take account of bandwidth. Or other costs. Could do dynamic routing, increasing cost when congested (big router queue).

Hierarchical routing: Large networks need large routings tables, which require more computation and bandwidth, hierarchical routing solves this. The idea is to divide network into a set of domains, gateways connect domains, computers within domain unaware of outside computers and gateways only know about other gateways.

External records: tell hosts in a domain which one to pick to reach a host in an external domain.

Summary records: Tell backbone which gateway to use to to reach an internal node.

The Internet: has three levels of routing, the highest is at the backbone level, connecting autonomous systems (AS). The next level is within AS, the lowest is within a LAN. The protocol between AS gate ways is the exterior gateway protocol, the protocol within AS is the interior gateway protocol.

EGP: The exterior gateway protocol is suspicious, and tells a border gateway who can be trusted and what paths are allowed. Interior protocols typically partition an AS into areas, and may involve converting from one scheme to another.

Routing information protocol: RIP is a distance vector routing algorithm. The cost metric is the hop count, and “infinity” (max number of hops in a table entry). Distance vectors exchange every 30 seconds. Split horizon. Simple, and ok for small subnets.

Open Shortest Path First: OSPF is a link state algorithm. It uses areas to route packets hierarchically within AS, it is complex and LSP databases need to be protected. It uses designated routers to reduce the number of end points.

Exterior Gateway Protocol: EGP is the original exterior gateway protocol, and is notionally distance vector. Costs are either 128 (reachable) or 255 (unreachable). Allows backdoors (set backdoor cost < 128).

Border Gateway Protocol: BGP is a path vector algorithm: a distance vector annotated with entire path, also with policy attributes, and is guaranteed to be loop free. Uses TCP to disseminate DV's.

Private Network Network Interface: PNNI is link state, has many levels of hierarchy, allows LSPs to be annotated with per link QoS metrics.

Routing within a broadcast LAN: On a broadcast LAN if a packet is meant for a destination within the LAN, if so either finds the datalink address or another routers data link address. On the Internet all hosts on the LAN have the same subnet address. A destinations datalink address is determined using ARP. Routers are discovered by periodically sending out router advertisements and routers are chosen based on the highest broadcast preference level. Redirection (ICMP) works by if a routers next hop is another router on he same LAN, the host gets a redirect message.

Multicast routing: Hosts are part of a multicast group, packets sent by any member of a group are received by all. Created either when a sender starts sending from a group or a receiver expresses interest in receiving. The expanding ring search is a way to use multicast groups for resource discovery, finding all resources TTL hops away. Ideally we want to send exactly one multicast packet per link, forming a multicast tree rooted at sender. Can prune tree to make more efficient, or graft to explicitly join the tree. Can translate class D to MAC address by copying IP address.

Internet Group Management Protocol: IGMP detects if a LAN has any members for a particular group. If there are no members, then we can prune the shortest path tree for that graph.

Wide Area Multicast: Distributes packets coming from any sender directed to a given group to all routers on the path to a group member. Works by assume each endpoint is a router which can use IGMP to discover all members of the LAN which want to subscribe to each multicast group. The simplest solution is to flood packets from a source to the entire network. If a router has not seen a packet before, it forwards it to all interfaces except the incoming one. Its simple and always works, but routers receive duplicate packets.

A clever solution is reverse path forwarding. Packets are forwarded from S to all interfaces iff a packet arrives on the interface that corresponds to the shortest path to S. Pruning tells routers in parent trees to stop forwarding packets to hosts that don't want it. If a host wants to receive messages after a previous prune, uses IGMP to tell of interest and floods a join message. Reverse path forwarding requires a router to have a routing table to know the shortest path to a source, but doesn't work if some routers don't support multicast. Need virtual links between multicast capable routers.Tunnels keep the broadcast address internally but put the packet destination as the next hop.

DVMRP: Distance vector multicast protocol is similar to RIP- its distance vector and uses the hop count metric. It is used with flood and prune (to determine memberships), reverse path forwarding (to decide where to forward a packet) and explicit join messages.

MOSPF: Is a multicast extension to OSPF. Routers flood group membership information with LSP's. Each router independently computes the shortest path tree that only includes multicast capable routers (so no need to flood and prune).

Core based trees: Avoid flood and prune by using a core router.

Policy routing: With policy routing paths are chosen depending on policy directives regarding things like the source and destination address, transit domains, quality of service, time of day, charging. Can have multiple metrics (eg time and cost) s long as all routers use the same rule in computing paths.

Crankback: Router returns a packet if no next hop with sufficient QoS guarantees can be found.

Mobile routing: Two problems of location (where is the host) and routing (how to get there). Mobile telephony uses ALOHCA up channel and talks to remote MTSO (closest base) which forwards to home MTSO. Mobile routing on the Internet uses tunnels to forward data, and doesn't go through home. Instead of slotted ALOHA registration packets are used. Security and loops are a problem.

Error Control:

CRC: Detects all single bit errors, almost all 2 bit errors, any odd number of errors, all bursts up to generator length. TCP/UDP/IP all use the same scheme: treat data as 16 bit integers, addd with end around carry, ones complement=check sum/

Packet errors: Different to bit errors, may have erasure, duplication (due to retransmission), insertion (packet from some other conversation), reordering (normally due to multiple paths or retransmission). Can be corrected by retransmission. Loss may be due to uncorrectable bit errors, buffer overflow. Can be detected by sequence numbers and timeouts, corrected by retransmission.

3 way handshake: SYN-SYN-ACK. Protects against delayed syns.

Timeouts: Even NACK's may be lost. If timer goes off, and no ACK, resend packet. Can expect a reply in about one RTT. Can set RTT statically, or dynamically using the exponential moving average RTT.

Retransmissions: Sender detects loss on timeout, which packets to retransmit. Error control window holds set of packets sent but not ACKed. On a timeout, retransmit the entire error control window (Go back N retransmission). Or selective retransmission where you remember non acked packets and only send them. SMART uses a cumulative sequence number.

Flow control:

Classification: With open loop the source describes its desired flow rate, the network admits the call then the source sends at this rate. With closed loop the source monitors available service rate and sends at this rate – due to speed of light delay errors are bound to occur. Hybrid asks for some minimum rate but can send more if available.

Peak rate: Highest rate at which a source can send data. For networks with fixed size packets its the minimum inter packet spacing, with variable sized packets its the highest rate over all intervals of a particular duration.

Average rate: The rate over some time period, either jumping window (send a bits over intervals of length t, regulator reinitializes ever interval) and moving window (regulator forgets packet sent more than t seconds ago).

Linear Bounded Arrival Process: The source bounds the # bits sent in any time interval by a linear function of time.

Leaky bucket: A regulator for an LBAP. Token bucket fills up at rate r, the max number tokens < s (data bucket size). If s is more, r is less.

End to end flow control: is cheaper, but hop by hop flow control is simpler and provides better control.

On-off flow control: If on, send at full speed. Ok when RTT is small, but what if OFF is lost.

Static Window: Allows multiple packets per RTT.

DECbit flow control: Every packet has a bit in header. Sink copies bit o ACK. If bits set, source reduces window size. In steady state, oscillate around optimal size. The router measures demand and mean queue length of each source. The source keeps track of bits and works with FIFO but requires per connection state.

TCP Flow control: Implicit, dynamic window, end to end. Similar to DECbit but no support from routers, additive increase multiplicative decrease. Window starts at 1, increases exponentially (slow start) then linearly. Halves every lack of ACK. Fast retransmit (duplicate cumulative ACKs).

NETBLT: First rate based flow control scheme. Separates error control (window) and flow control (no coupling).

Packet Pair: Improves on NETBLT, better measurement of bottleneck, control based on prediction, finer granularity. ACKs give time series of service rates in the past, can be used to reduct the next rate.

ATM Forum End to End Rate based Flow Control: EERC is similar to DECbit but sends a whole cells worth of info instead of one bit. Source periodically sends a resource management cell with a rate request.

Comparisons: Flow control is easier with RR scheduling. Explicit schemes are more robust. Hop byhop schemes are more responsive, but more complex. Try to separate error control and flow control. Rat based schemes are inherently unstable unless well engineered.

Hybrid flow control: Source gets a minimum rate, but can use more. All problems of both open and closed loop flow control.

Common Protocols:

Telephone network: Uses MTP to control the physical and datalink layers, ISDN to control the app layer. Trunks multiplex together numerous DS0 (64kbps single call).

Plesiochronous hierarchy: Nearly synchronous. If multiplexing together different streams, the output always runs a bit faster. Overhead is added to be able to identify bits from a particular stream. Used everywhere except DS1 and DS0.

SDH: Synchronous hierarchy using atomic clocks. Overhead in headers, use pointers if sending too flow/fast.

Signaling System 7: Application service element (eg authenticates users), message transfer parts on lower OSI layers. MTP headers contain flags, destination, length etc.

Internet: HTTP (App layer), Sockets/Streams (Session layer), TCP/UDP (transport layer), IP (Network layer).

IP: Unreliable, best effort, end to end. Ipv4 packets contain type of service TOS, TTL, protocol, checksum, flags, source, destination, data. Can fragment then ressemble at receiver. TTL is decremented on each hop and every 500ms. If TTL is decremented to 0 and ICMP error packet is sent- used for tracert. Ipv6 contains less headers, but can insert more.

TCP: Multiplexed, duplex, connection orientated, reliable, flow controlled, byte steam. Packets contain sequence, ack numbers, flags, window size, checksum, source+destination port.

UDP: Simpler, source and destination port, length, checksum.

HTTP: Get, head, post, delete, connect, trace, options commands. Responds with status, headers then body. Initially stateless, but not so now due to cookies.

ATM stack: ATM over data link, UNI/PNNI over application. Connection orientated, in sequence, unreliable, QoS assured. Packets contain VCI which set virtual paths. Network layer is AAL. AAL1 is for synchronous apps (provides timestamps, clocking, FEC). AAL ¾ for data trafic, provides error detection, segmentation, reassembly. AAL 5 is fast, bit in header means end of frame, provides CRC. SSCOP used for transport layer, provides error and flow control. SSCOP works without ACKs, sender polls and receiver sends status. Can do IP over ATM by ignoring QoS, problems due to ATM being connection orientated and different addressing schemes. IP encapsulation over ATM by putting data portion of IP packets into an AAL5 frame, or entire IP packet into AAL5 frame. Next hop routing stores IP to ATM address translations independent of subnet boundaries. Use multicast address resolution (MARS) server to translate Class D addresses that correspond to endpoints. Can emulate LAN by translating MAC address to ATM address. Cells in Frame (CIF) can reuse a Ethernet card.

Protocol Implementation: Want to optimize the common case, watch for bottle necks,optimize inner loops, data structures, cache hints, send large packets and use hardware.

Monolithic in kernel: Application in user space, everything else (session downwards) in kernel.

Monolithic in user space: Application, transport, network, device driver all in user space, connecting to proxy and device in kernel. Can also have per process in user space using registry service.

Single context: From device driver to device, from device to session.

Tasks: Put applications into buffer pool.

Upcalls: Send and receive between layers.

Multiple Access:

The multiple access problem: Eg at an audio conference want to maximize exchange of information, time spent waiting to speak is minimized. Can either use a moderator, or just speak when noone else is speaking. Need to choose a base topology (Frequency, time or code division multiple access) to isolate traffic from different stations.

Performance metrics: Normalized throughput is the fraction of link capacity used to carry non retransmitted packets. The mean delay is the amount of time a station must wait before it successfully transmits a packet. Stable algorithms don't reduce throughput with increased load. Fairness.

Frequency division multiple access: FDMA is the simplest, suited for analog links, each stations has its own frequency band. Receivers tune to the right frequency. Up and down link use different frequencies.

Time division multiple access: All stations transmit on the same frequency, but at different times.

Code division multiple access: Users separated by both time and frequency, can frequency hop or convert single bits to codes. Complex but secure.

Centralized access schemes: One station is master, normally with highest power.

Polling: Master asks each station in turn if it wants to send.

Probing: Master does binary search of addresses to locate next active station.

Circuit mode: When station wants to transmit, sends a message to master using packet mode. Used in cellular phones.

Reservation based schemes: When distance is large (eg satellites) cant use a distributed scheme due to collisions. Stations contend for a minislots (used only for reservations), master decides winners.

Distributed systems: More reliable, more complicated. Decentralized polling works the same, each station assigned a slot that it may use. With decentralized probing all stations in left subtree of root place packet on medium, if there is a collision then the root moves to the left.

Carrier Sense Multiple Access: CSMA scheme works by checking whether a medium is in use before sending. Can either choose a probability to send if detected idle, or exponentially backoff on collisions. Eg if a medium is busy, wait a random amount of time (within limits) on timeout send a packet and wait for an ack. If no ack, assume packet is lost.

Ethernet: Ethernet uses CSMA with exponential back off and a maximum packet size of 1500 bytes to prevent hogging. Hubs build ethernet in a box. With switched ethernet each station is connected to a switch, data has to be buffered. Easy to setup and robust to noise, but cant guarantee good service in heavy loads.

Busy Tone Multiple Access: BTMA works when CSMA wont as terminals are hidden or exposed (can't hear all other broadcasts). Uses a separate busy tone channel.

Multiple Access Collision Avoidance: Send request to send, station sends clear to send if ok. Other stations listen in.

Token passing: Pass on after finished transmitting. Stops starvation. Need to regenerate token if disappears. With double rings there is not single point of failure mode. FDDI is the most popular token ring base LAN.

Hub or star rings: Used in real life, simplifies. Active hub is predecessor and successor to every station.

ALOHA: Just send and wait for an ACK. If no ack, then try again after a random waiting time. By making sure transmissions start on a slot boundary can double ALOHA's capacity. Can combine with reservation ALOHA to contend for minislots. Used for cable modem uplinks.

Switching: Switches need to build routing tables, resolve contention for output trunks through scheduling and admission control. Switches want to maximize capacity, minimize call blocking (due to being unable to find a path or no space in output frame) and minimize packet loss (due to no buffer space).

Packet switching: Have headers, as opposed to samples which don't.

Connection orientated switching: Requires a setup phase in the control plane.

A generic switch: Input buffers -> Port Mapper -> Switch fabric -> Output buffers

Circuit switching: Moving samples from an input port to and output port. Destination depends on time it arrives, that is the relative order in a frame. Need to demultiplex, then switch, then multiplex. Multistage crossbar: Space division switching, each different time has different possible cross points.

Packet switching: Look up destination address in datagram, or VCI in cell.

Repeaters: At physical level.

Bridges: At datalink level, discovers attached stations by listening.

Routers: At network level, participate in routing protocols.

Application level gateways: Treat entire network as a single hop.

Port mappers: Lookup output port based on destination address, using Tries (address trees) and caching recently used addresses in a CAM.

First generation switch: Bottleneck may be CPU.

Second generation switch: Put intelligence into line cards to port map. Bottleneck is bus.

Third generation switches: Uses parallel paths (fabric) to reduce bottleneck of ring. Output buffer is a point of contention.

Switch fabrics: Transfer data from input to output, ignoring scheduling and buffering. May use buffered crossbar. Packets are tagged with output port #. A basic fabric element will send to upper output if 0, to lower if 1. To buffer or drop if both packets to same output. Banyan is the simplest, self routing recursive fabric. Can avoid blocking by choosing order in which packets appear at input ports. Can merge. With small fixed packet sizes in ATM you can easily build large parallel fabrics.

Buffer placement: With input buffering, no speedup in buffers or trunks. You also get head of line blocking. Output queuing doesn't suffer from head of line blocking, but buffers need to run faster than trunk speed. With shared input and output memory only need to route header to the output port, but get bottleneck in time taken to read and write multiported memory. By doing wide read and writes can reduce cost. You can buffer fabric in each switch element but is expensive and requires scheduling. Normally put buffers in many points.

Multicasting: Can do in hardware, need to generate and distribute copies, and need to do VCI translation for copies.

Integrated Services:

Support for real time services: IP isn't designed for QoS, need to add in features to do this. Routers need to give preferential treatment to real time packets. Also need to extend transport protocols and application signaling.

Problems with IP: Individual packets, no recognition of flows and connectionless so no signaling. No priority traffic. Dynamic routing changes to unfixed QoS.

Integrated Services Packet Network: Service type QoS descriptions. Signaling in routing. Admission control to control access to resources. Scheduling allows prioritisation of certain traffic.

Network hierarchy: Local access network has low multiplexing and low volume of traffic. Distribution network has more, and the core network backbone has the most.

Autonomous Systems: Use intradomain routing and have their own internal policy, using a protocol such as RIP or OSPF. Inter domain routing is done through BGP.

Delay: Due to prorogation speed (speed of light), transmission (data rate of network interfaces), network elements (buffering, processing), end system processing (application specific).

Jitter: Variation in delay produces variable packet arrival rate due to route changes, changing congestion etc.

Loss: If non real time just retransmit like with TCP, with real time either forward error code of produce special redundant packet. Can be due to congestion etc.

Data rate: Short and long term changes, due to network load and routing changing. As multiplexed varies with overall load and link sharing rules.

Elastic applications: Interactive eg X-Windows. Interactive bulk eg FTP. Asynchronous eg Email. Inelastic may be tolerant and adaptive to either delay or rate.

Delay: Can find max and min end to end delay. Max jitter is about D_MAX – D_MIN.

Leaky bucket: Bucket size (bytes) and Leak rate (B/S). Data pours in and is leaked out, to get consistent rate.

Token bucket: Bucket size which fills up without limits and is emptied at peak rate, tokens come in at bucket rate. Only transmits data from bucket at peak rate when there is a token.

INTSERV: Application defines service level, and tells the network using signalling. The network then applies admission control and checks if reservation is possible, then routers allocate and control resource in order to honor request. RSVP Signaling protocol. Service templates describe describe Tspec traffic patterns and Rspec service requests. A token bucket is used. The controlled load specification provides probabilistic best effort guarantee under unloaded conditions. The guaranteed service definition provides assured data rate with bounded delaym but not guarantees on jitter. Requires a RSPec to define required service rate and the delay bound.

RSVP: Provides user-network and network-network signaling. Traffic information is sent via a Tspec into the network. The receiver confirms reservation.

Sender: Path message. Receiver: Resv Message (and Tspec and RSPec).

Sender: PathTear. Receiver: ResvTear.

Uses FilterSpec style of reservation if using fixed filter. If using wildcard filter FilterSpec isn't required. If using Shred explicit then FilterSpec is required.

Reservations may block one another, need soft state reservations. Under router failure QoS degrades to best effort, and need to renegotiate QoS. Applications need to be RSVP aware.

DIFFSERV: Uses differentiated services: tiered service levels. Packets are marked by the network not application, and is easier to introduce onto current networks than INTSERV. Can have premium (low delay) or assured (high data rate, low loss) service classes. Uses service level agreements between user and provider. Puts DS byte into IP packets. Expediated forwarding has low delay, low jitter, low loss. Assured forwarding has different classes of assurance. Diffserv has no standards for service level agreements and provides unsymmetric QoS.

UDP: Connectionless, unreliable, unordered, datagram, no error control, no flow control, no congestion control. RTP and RTCP (real time control protocol) are carried in UDP packets and provide no QoS guarantees. RTP header contains sequence number, timestamp source etc. RTCP sends status report messages.

Scheduling:

Traditional routing: Individual packets, no recognition of flows, no signaling (connectionless). No examination of type of traffic, so no priority traffic.

Router: Service: Packet forwarding. Scheduled resource: Output Queues. Service requests: Packets arriving on input lines.

Simple router: No input buffer, only output buffer (queue), FCFS scheduling.

Conservation law: Reducing delay of one flow, increases delay of others. Non work-conserving schedulers can be idle even if packets waiting, to smooth packet flows.

Max-min fair share criteria: Flows are allocated resource in order of increasing demand. Flows get no more than they need.

Simple priority queuing: Just have lots of queues, some greater priority than others. Simple but not max min fair: starvation of low priority queues.

Generalized processor sharing: GPS is work conserving and max-min fair. Visit flows round robin. Not real, just used to compare against other schedulers.

Weighted round robin: WRR is the simplest attempt at GPS. Queues are visited in round robin in proportion to weights assigned. Bigger packet size, smaller weight.

Deficit Round Robin: With DRR queues not served build up credits.

Weighted Fair Queuing: Packets tagged with finish number (time they would have finished under GPS), those with smallest time served first. Finish number if highest current finish number for queue + number of bits in packet.

Class based queuing: Link tree, child can borrow and space capacity from parent. Can prioritize real time.

Queue management: Ensuring buffers available, organizing packets in a queue, packet dropping when queue is full, congestion control.

Packet dropping policies: Drop from tail: Simple. Drop from head: Old packets purged first, good for real time. Random drop: May be fair. Flush queue: Drop all, flows should back off. Intelligent drop: Look in packets.

Packet drops: TCP (non real time) sees congestion, slows down. Then does slow start and congestion avoidance. All ok. UDP (real time) needs to fill in at receiver, tries to adapt.

Random Early Detection: RED spots congestion before it happens, sees dropped packets as a preemptive congestion control signal and the source slows down. Packets can be dropped or marked as offending (likely to be dropped by RED aware routers). Requires adaptive sources.

IP Multicast: One transmission, many receivers. Uses a Class D IP address. Non group members can send to group. Requires multicast capable routers. IGMP: Group membership control. On a LAN need to translate to MAC address.

MBONE: Distance vector multicast routing. Routers aren't multicast aware, uses a virtual network. Uses IP tunneling.

MOSPF: Link state algorithm, intended for larger networks. Soft-state: Router advertisement sent on group join.

CBT: Uses core router. Leaf sends IGMP request, local router sends join request to core. Join request routed to core via normal unicast.

PIM: Can use any unicast routing protocol info. Dense (RPM, flood and prune with explicit join) and sparse mode (similar to CBT, core with explicit graft to tree).

Multicast addresses: 224.0.0.1 sends to all systems on this sub net.

224.0.0.2 sends to all routers on this sub net.

224.0.0.4 sends to all DVMRP routers.

Multimedia Conferencing: Use IP multicast. Per application session two RTCP channels. Gateways do transcoding to do multicast to unicast, ISDN supports dial up users.

ToS byte: Can set to minimize delay, throughput, reliability, cost or normal.

Multiple protocol label switching: Fast forwarding, helps scaling and performance. Adds complexity in routers.

Traffic Management:

Utility function: Assume users all have a utility function that they want to maximize.

U= S – a t

u = utility from file transfer, S = satisfaction when transfer infinitely fast, t = transfer time, a = rate at which satisfaction decreases with time. If t> S/a then user is worse off.

Economic principles: Cheaper to have single network than different networks for different QoS, as unused capacity can be shared. Better to reduce delay for delay insensitive applications.

Traffic classes: Telnet requires low bandwidth and low delay. ATM forum subclasses: Available Bit Rate ABR (users get whatever is available, zero loss if network signals obeyed, no guarantee on delay or bandwidth) and Unspecified Bit Rate (cheaper, no feedback).

Time scales: Less than one round trip time (cell level): scheduling and buffer management, regulation and policing, routing (for connectionless). One or more found trip times (burst level): feed back flow control, transmission, renegotiation. Session (call level): signaling, admission control, pricing, routing (for connection based). Day: peak load pricing. Weeks: capacity planning.

Renegotiation: An option for guaranteed service traffic. Bursts. Matches service rate to traffic. Doing so once every 10 seconds reduces bandwidth to about average rate.

RCBR: All traffic sent as CBR. Buggers at edge of network.

Signaling: Involves how to carry the message (transport) and how to interpret (semantics). Classically setup, setup_ack, setup_response. Need to translate resource requirements, eg end to delay bound of 100ms – what should be bound at each hop?

Multicast reservation styles: naïve multicast (source initiated). Intelligent multicast: Two messages per link of spanning tree. Naïve multi point multi cast: Two messages per source per link.

RSVP: Receiver initiated. Reservation state per group, instead of per connection. Path and Resv messages.

Soft state: State in routers is periodically refreshed.

CBR admission control: On failure try again, reroute, or hold.

VBR admission control: Peak rate differs from average rate (burstiness). Peak rate admission control: Reserve at a connections peak rate. Worst case admission control: Characterize source by average rate and burst size. Admission with statistical guarantees: The more sources, the more smooth the burstiness. Measurement based admission: Measure average load.

Peak load pricing: Cyclic demand, shift demand to off peak times using pricing.

Capacity planning: Measure network during buy hour. Create traffic matrix. Decide topology. Assign capacity.

Erlang curves: Probability of blocking in telephone networks.

Resource translation: Easy to work out bandwidth, hard to do delay.

Measurement based admission: For traffic that can't describe itself.

Peak load pricing: How to choose off and on peak times and prices.

Either align service to users better, or just spend the money on overprovisionoing.

Mobile problems: Variable delay, throughput, loss. Shared media. Access patterns different to fixed. Many wireless links very saturated.

Management: User account management, QoS auditing, risk analysis, security.

Routers: Maintain routes. Forward packets based on routing information.

Forwarding: Moving a packet from an input port to an output port. Make a forwarding decision based on route information.

Multiple Protocol Label Switching: MPLS involves fast forwarding and helps scaling. Intended for ATM. Supports unicast, multicast, QoS, source routing. Uses label switch router – simple, fast link level forwarding. At each new hop a new label is assigned. Forwarding equivalence class (FEC) means packets that share the same next hop share the same label locally.