Random随机，按权重设置随机概率。在一个截面上碰撞的概率高，但调用量越大分布越均匀，而且按概率使用权重后也比较均匀，有利于动态调整提供者权重。
2.轮询及加权轮询
轮询(RoundRobbin)当服务器群中各服务器的处理能力相同时，且每笔业务处理量差异不大时，最适合使用这种算法。轮循，按公约后的权重设置轮循比率。存在慢的提供者累积请求问题，比如：第二台机器很慢，但没挂，当请求调到第二台时就卡在那，久而久之，所有请求都卡在调到第二台上。加权轮询(Weighted Round Robbin)为轮询中的每台服务器附加一定权重的算法。比如服务器1权重1，服务器2权重2，服务器3权重3，则顺序为1-2-2-3-3-3-1-2-2-3-3-3- ......
3.最小连接及加权最小连接
最少连接(LeastConnections)在多个服务器中，与处理连接数(会话数)最少的服务器进行通信的算法。即使在每台服务器处理能力各不相同，每笔业务处理量也不相同的情况下，也能够在一定程度上降低服务器的负载。
加权最少连接(WeightedLeastConnection)为最少连接算法中的每台服务器附加权重的算法，该算法事先为每台服务器分配处理连接的数量，并将客户端请求转至连接数最少的服务器上。
4.哈希算法
一致性Hash，相同参数的请求总是发到同一提供者。当某一台提供者挂时，原本发往该提供者的请求，基于虚拟节点，平摊到其它提供者，不会引起剧烈变动。
5.IP地址散列
通过管理发送方IP和目的地IP地址的散列，将来自同一发送方的分组(或发送至同一目的地的分组)统一转发到相同服务器的算法。当客户端有一系列业务需要处理而必须和一个服务器反复通信时，该算法能够以流(会话)为单位，保证来自相同客户端的通信能够一直在同一服务器中进行处理。
6.URL散列
通过管理客户端请求URL信息的散列，将发送至相同URL的请求转发至同一服务器的算法。
解决方案在多个用户并发访问台服务器的时候，服务器可能会出现性能下降甚至宕机的情况。为解决此种情况，我们组提出的方案是将用户的访问流量分担不同的服务器上，也就是负载均衡的实现。目前传统网络的负载均衡存在硬件设备高成本和架构难的特点。因此我们的方案是用软件定义网络（SDN）来实现网络流量的负载均衡。在独立的SDN控制器POX控制器，通过python脚本实现与部署该方案。
一、负载均衡架构 SDN的负载均衡的实现架构部署为三层，分别为数据层、控制层、应用层。POX控制器用Restful API实现南向接口连接控制层与应用层，北向接口连接至Mininet软件的拓扑网络。主机以GET方法请求POX控制器的内容，POX控制器监测网络数据并下发流表到各个交换机，交换机按照流标进行数据传输，选择不同的服务器，完成流量的负载均衡，增大吞吐量，减少服务端的压力。如图所示为三层架构。
ip_loadbalancer.py
官方随机算法实现的一种负载均衡代码如下
展开查看 #Copyright 2013,2014 James McCauley # #Licensed under the Apache License, Version 2.0 (the "License"); # you may not use this file except in compliance with the License. #You may obtain a copy of the License at: # # # #Unless required by applicable law or agreed to in writing, software #distributed under the License is distributed on an "AS IS" BASIS, # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. #See the License for the specific language governing permissions and #limitations under the License. """ A very sloppy IP load balancer. Run it with --ip= --servers=IP1,IP2,... By default, it will do load balancing on the first switch that connects. If you want, you can add --dpid= to specify a particular switch. Please submit improvements. :) """ from pox.core import core import pox log = core.getLogger("iplb") from pox.lib.packet.ethernet import ethernet, ETHER_BROADCAST from pox.lib.packet.ipv4 import ipv4 from pox.lib.packet.arp import arp from pox.lib.addresses import IPAddr, EthAddr from pox.lib.util import str_to_bool, dpid_to_str, str_to_dpid import pox.openflow.libopenflow_01 as of import time import random FLOW_IDLE_TIMEOUT = 10 FLOW_MEMORY_TIMEOUT = 60 * 5 class MemoryEntry (object): """ Record for flows we are balancing Table entries in the switch "remember" flows for a period of time, but rather than set their expirations to some long value (potentially leading to lots of rules for dead connections), we let them expire from the switch relatively quickly and remember them here in the controller for longer. Another tactic would be to increase the timeouts on the switch and use the Nicira extension which can match packets with FIN set to remove them when the connection closes. """ def __init__ (self, server, first_packet, client_port): self.server = server self.first_packet = first_packet self.client_port = client_port self.refresh() def refresh (self): self.timeout = time.time() + FLOW_MEMORY_TIMEOUT @property def is_expired (self): return time.time() > self.timeout @property def key1 (self): ethp = self.first_packet ipp = ethp.find('ipv4') tcpp = ethp.find('tcp') return ipp.srcip,ipp.dstip,tcpp.srcport,tcpp.dstport @property def key2 (self): ethp = self.first_packet ipp = ethp.find('ipv4') tcpp = ethp.find('tcp') return self.server,ipp.srcip,tcpp.dstport,tcpp.srcport class iplb (object): """ A simple IP load balancer Give it a service_ip and a list of server IP addresses. New TCP flows to service_ip will be randomly redirected to one of the servers. We probe the servers to see if they're alive by sending them ARPs. """ def __init__ (self, connection, service_ip, servers = []): self.service_ip = IPAddr(service_ip) self.servers = [IPAddr(a) for a in servers] self.con = connection self.mac = self.con.eth_addr self.live_servers = {} # IP -> MAC,port try: self.log = log.getChild(dpid_to_str(self.con.dpid)) except: # Be nice to Python 2.6 (ugh) self.log = log self.outstanding_probes = {} # IP -> expire_time # How quickly do we probe? self.probe_cycle_time = 5 # How long do we wait for an ARP reply before we consider a server dead? self.arp_timeout = 3 # We remember where we directed flows so that if they start up again, # we can send them to the same server if it's still up. Alternate # approach: hashing. self.memory = {} # (srcip,dstip,srcport,dstport) -> MemoryEntry self._do_probe() # Kick off the probing # As part of a gross hack, we now do this from elsewhere #self.con.addListeners(self) def _do_expire (self): """ Expire probes and "memorized" flows Each of these should only have a limited lifetime. """ t = time.time() # Expire probes for ip,expire_at in self.outstanding_probes.items(): if t > expire_at: self.outstanding_probes.pop(ip, None) if ip in self.live_servers: self.log.warn("Server %s down", ip) del self.live_servers[ip] # Expire old flows c = len(self.memory) self.memory = {k:v for k,v in self.memory.items() if not v.is_expired} if len(self.memory) != c: self.log.debug("Expired %i flows", c-len(self.memory)) def _do_probe (self): """ Send an ARP to a server to see if it's still up """ self._do_expire() server = self.servers.pop(0) self.servers.append(server) r = arp() r.hwtype = r.HW_TYPE_ETHERNET r.prototype = r.PROTO_TYPE_IP r.opcode = r.REQUEST r.hwdst = ETHER_BROADCAST r.protodst = server r.hwsrc = self.mac r.protosrc = self.service_ip e = ethernet(type=ethernet.ARP_TYPE, src=http://www.likecs.com/self.mac, dst=ETHER_BROADCAST) e.set_payload(r) #self.log.debug("ARPing for %s", server) msg = of.ofp_packet_out() msg.data = e.pack() msg.actions.append(of.ofp_action_output(port = of.OFPP_FLOOD)) msg.in_port = of.OFPP_NONE self.con.send(msg) self.outstanding_probes[server] = time.time() + self.arp_timeout core.callDelayed(self._probe_wait_time, self._do_probe) @property def _probe_wait_time (self): """ Time to wait between probes """ r = self.probe_cycle_time / float(len(self.servers)) r = max(.25, r) # Cap it at four per second return r def _pick_server (self, key, inport): """ Pick a server for a (hopefully) new connection """ return random.choice(self.live_servers.keys()) def _handle_PacketIn (self, event): inport = event.port packet = event.parsed def drop (): if event.ofp.buffer_id is not None: # Kill the buffer msg = of.ofp_packet_out(data = event.ofp) self.con.send(msg) return None tcpp = packet.find('tcp') if not tcpp: arpp = packet.find('arp') if arpp: # Handle replies to our server-liveness probes if arpp.opcode == arpp.REPLY: if arpp.protosrc in self.outstanding_probes: # A server is (still?) up; cool. del self.outstanding_probes[arpp.protosrc] if (self.live_servers.get(arpp.protosrc, (None,None)) == (arpp.hwsrc,inport)): # Ah, nothing new here. pass else: # Ooh, new server. self.live_servers[arpp.protosrc] = arpp.hwsrc,inport self.log.info("Server %s up", arpp.protosrc) return # Not TCP and not ARP. Don't know what to do with this. Drop it. return drop() # It's TCP. ipp = packet.find('ipv4') if ipp.srcip in self.servers: # It's FROM one of our balanced servers. # Rewrite it BACK to the client key = ipp.srcip,ipp.dstip,tcpp.srcport,tcpp.dstport entry = self.memory.get(key) if entry is None: # We either didn't install it, or we forgot about it. self.log.debug("No client for %s", key) return drop() # Refresh time timeout and reinstall. entry.refresh() #self.log.debug("Install reverse flow for %s", key) # Install reverse table entry mac,port = self.live_servers[entry.server] actions = [] actions.append(of.ofp_action_dl_addr.set_src(self.mac)) actions.append(of.ofp_action_nw_addr.set_src(self.service_ip)) actions.append(of.ofp_action_output(port = entry.client_port)) match = of.ofp_match.from_packet(packet, inport) msg = of.ofp_flow_mod(command=of.OFPFC_ADD, idle_timeout=FLOW_IDLE_TIMEOUT, hard_timeout=of.OFP_FLOW_PERMANENT, data=event.ofp, actions=actions, match=match) self.con.send(msg) elif ipp.dstip == self.service_ip: # Ah, it's for our service IP and needs to be load balanced # Do we already know this flow? key = ipp.srcip,ipp.dstip,tcpp.srcport,tcpp.dstport entry = self.memory.get(key) if entry is None or entry.server not in self.live_servers: # Don't know it (hopefully it's new!) if len(self.live_servers) == 0: self.log.warn("No servers!") return drop() # Pick a server for this flow server = self._pick_server(key, inport) self.log.debug("Directing traffic to %s", server) entry = MemoryEntry(server, packet, inport) self.memory[entry.key1] = entry self.memory[entry.key2] = entry # Update timestamp entry.refresh() # Set up table entry towards selected server mac,port = self.live_servers[entry.server] actions = [] actions.append(of.ofp_action_dl_addr.set_dst(mac)) actions.append(of.ofp_action_nw_addr.set_dst(entry.server)) actions.append(of.ofp_action_output(port = port)) match = of.ofp_match.from_packet(packet, inport) msg = of.ofp_flow_mod(command=of.OFPFC_ADD, idle_timeout=FLOW_IDLE_TIMEOUT, hard_timeout=of.OFP_FLOW_PERMANENT, data=event.ofp, actions=actions, match=match) self.con.send(msg) #Remember which DPID we're operating on (first one to connect) _dpid = None def launch (ip, servers, dpid = None): global _dpid if dpid is not None: _dpid = str_to_dpid(dpid) servers = servers.replace(","," ").split() servers = [IPAddr(x) for x in servers] ip = IPAddr(ip) #We only want to enable ARP Responder *only* on the load balancer switch, #so we do some disgusting hackery and then boot it up. from proto.arp_responder import ARPResponder old_pi = ARPResponder._handle_PacketIn def new_pi (self, event): if event.dpid == _dpid: #Yes, the packet-in is on the right switch return old_pi(self, event) ARPResponder._handle_PacketIn = new_pi #Hackery done. Now start it. from proto.arp_responder import launch as arp_launch arp_launch(eat_packets=False,**{str(ip):True}) import logging logging.getLogger("proto.arp_responder").setLevel(logging.WARN) def _handle_ConnectionUp (event): global _dpid if _dpid is None: _dpid = event.dpid if _dpid != event.dpid: log.warn("Ignoring switch %s", event.connection) else: if not core.hasComponent('iplb'): # Need to initialize first... core.registerNew(iplb, event.connection, IPAddr(ip), servers) log.info("IP Load Balancer Ready.") log.info("Load Balancing on %s", event.connection) # Gross hack core.iplb.con = event.connection event.connection.addListeners(core.iplb) core.openflow.addListenerByName("ConnectionUp", _handle_ConnectionUp) 解决方案